[2019 KAKAO BLIND RECRUITMENT] 실패율 | Python3

실패율은 n의 개수/n과 같거나 큰 원소 개수를 구하면 된다.  stages에서 n의 개수, n과 같거나 큰 원소의 개수를 구하기 위해 count 함수를 사용하는 것은 시간복잡도가 O(n)이므로 이진 탐색을 활용해 문제를 풀었다. Python3 내장 모듈인 bisect_right 함수를 사용하였다. 1,2,3,...N 순차적으로 실패율을 구할 때 n보다 작은 숫자에 대해서는 탐색할 필요가 없으므로 인덱싱을 통해 이진 탐색할 범위를 줄여나갔다. 

 

 

from bisect import bisect_right
def solution(N, stages):
    s, f, length, l, r = sorted(stages), [], len(stages), 0, 0
    for n in range(N):
        l+=r; r=bisect_right(s[l:],n+1)
        f.append(r/(length-l) if length>l else 0)
    return [x[0]+1 for x in sorted(enumerate(f), key=lambda x: -x[1])]

             

count, 인덱싱을 활용한 다른 풀이와 시간 비교

 

프로그래머스 다른 사람의 풀이에서 가장 많은 사람들이 푼 count, 인덱싱 코드와 시간을 비교하니 이진탐색으로 푼 시간이 훨씬 빠름을 볼 수 있다. 그 외에도 우선순위큐, Counter 딕셔너리 등등 다양한 방법의 풀이가 많았다.