[2019 KAKAO BR] 실패율

실패율

• 실패율 (스테이지 도달, 아직 클리어하지 못한 플레이어수)/(스테이지 도달 플레이어수)
• 전체 스테이지 개수는 N (1 ~ N)
• stages 배열에는 현재 사용자가 플레이중인 스테이지의 번호가 담겨있음
• 실패율이 높은 스테이지부터, 내림차순으로 배열 리턴
• 실패율이 같은 스테이지는, 스테이지 번호가 작은것부터 리턴
• 스테이지 번호가 N+1 이면 모든 스테이지를 클리어 했다는 의미

Solution

• 실패율의 분모는 stages 배열에서 해당 스테이지를 카운트한 결과
• 실패율의 분자는 높은 스테이지 부터 해당 스테이지까지 누적된 사용자의 카운트 결과
• 실패율=>내림차순, 스테이지번호=>오름차순

Code

from collections import Counter
def solution(N, stages):

    cnt = Counter(stages)
    acc = cnt[N+1] # 없으면 0

    results = []
    for i in range(N, 0,-1):
        acc += cnt[i]
        fail_rate = 0 if cnt[i]==0 else cnt[i]/acc
        results.append((-fail_rate,i))        

    results.sort()        
    return [ res[1] for res in results] 

시간복잡도

• O(N) : 카운팅
• O(N) : for 반복문
• O(NlogN) : 소팅