[프로그래머스/Lv.1] 실패율_2019 KAKAO BLIND RECRUITMENT

프로그래머스

---

풀이1

def solution(N, stages):
    # 1. 실패율 계산 : 해당 스테이지에 도전중인 사용자 수/(전체-해당 스테이지 미만 도전중인 사용자 수)
    failure = [0] * (N+1)
    for stage in range(1, N+1):
        under_stage = 0
        for i in range(stage):
            under_stage += stages.count(i)
        failure[stage] = stages.count(stage)/(len(stages) - under_stage)
    
    # 2. 정렬
    temp = []
    for tp in enumerate(failure):
        temp.append(list(tp))
    temp.sort(key=lambda x: -x[1])
    
    # 3. 인덱스만 뽑아내기
    answer = []
    for i in range(N+1):
        if temp[i][0] != 0:
            answer.append(temp[i][0])
        
    return answer

런타임 에러 및 시간초과 발생

• 27 中 12 케이스 통과
• 27 中 9 케이스 시간초과
• 27 中 6 케이스 런타임 에러

 

시간복잡도

count 메소드는 리스트에서 특정 요소의 개수를 세는 메소드이다.

count 메소드를 호출하면, 리스트를 처음부터 끝까지 순회하며 해당 요소를 찾으면 count를 1 증가시킨다.

따라서 count 메소드를 한 번 호출할 때 마다 시간복잡도는 O(N)이 된다.

위 코드에서는 for문으로 리스트 요소를 순회하며 count 메소드를 호출하므로 O(N^2)의 시간복잡도를 가진다.

---

풀이2

def solution(N, stages):
    user = len(stages)
    
    # 카운팅 배열 -> 각 스테이지별로 도전 중인 사용자의 수 
    cnt = [0] * (N+2)
    for num in stages:
        cnt[num] += 1
    
    # 누적 카운팅 배열 -> 이전 스테이지 모두 누적하여, 도전 중인 사용자의 수
    tot = [0] *(N+2)
    tot[1] = cnt[1]
    for i in range(2, N+2):
        tot[i] = tot[i-1] + cnt[i]
    
    # 실패율 딕셔너리 -> '스테이지' : 실패율
    fail = dict()
    for i in range(1, N+1):
        fail[i] = cnt[i]/(user-tot[i-1])
    
    # 실패율 딕셔너리 값을 기준으로 내림차순 정렬
    answer = []
    new_fail = sorted(fail.items(), key=lambda x: x[1], reverse=True)
    for tup in new_fail:
        answer.append(tup[0])
    return answer

런타임 에러 발생

• 27 中 8 케이스 런타임 에러

 

시간복잡도

시간초과를 해결하기 위해 for문 + count메서드 → 카운팅 배열로 바꾸었다.

시간복잡도를 줄이기 위해 enumerate를 딕셔너리로 바꾸었지만 사실 이건 상관없다.. ㅎ

---

정답 풀이1

def solution(N, stages):
    user = len(stages)
    
    # 카운팅 배열 -> 각 스테이지별로 도전 중인 사용자의 수 
    cnt = [0] * (N+2)
    for num in stages:
        cnt[num] += 1
    
    # 누적 카운팅 배열 -> 이전 스테이지 모두 누적하여, 도전 중인 사용자의 수
    tot = [0] *(N+2)
    tot[1] = cnt[1]
    for i in range(2, N+2):
        tot[i] = tot[i-1] + cnt[i]
    
    # 실패율 딕셔너리 -> '스테이지' : 실패율
    fail = dict()
    for i in range(1, N+1):
        deno = user-tot[i-1]
        if deno:
            fail[i] = cnt[i]/deno
        else:
            fail[i] = 0
    
    # 실패율 딕셔너리의 값을 기준으로 내림차순 정렬
    answer = []
    new_fail = sorted(fail.items(), key=lambda x: x[1], reverse=True)
    for tup in new_fail:
        answer.append(tup[0])
    return answer

 

런타임 에러

실패율을 계산할 때 분모는 '전체 사용자 - 이전 스테이지를 도전 중인 사용자' 가 된다. 그런데 직전 스테이지까지 도달한 사용자 수가 전체 사용자 수와 일치한다면 분모가 0이 되어 ZeroDivisionError가 발생한다. 

 

예를 들어, 8명의 사용자와 5 스테이지까지 있을 때 모든 사용자들이 아직 3 스테이지까지만 도달했다고 하자.

4 스테이지의 실패율은 다음과 같다.

실패율 = 0 / ( 8 - 8 )

따라서 if문을 사용해서 위 같은 경우를 처리해주어야한다.