[프로그래머스] 실패율 풀이

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/42889

2. 풀이

2.1. lower_bound, upper_bound를 사용하여 해결한 풀이

먼저 배열을 정렬합니다. c++의 lower_bound, upper_bound 와 같은 함수로 bisect_left, bisect_right 함수가 존재합니다.
위의 함수들을 이용하여 찾고자 하는 숫자의 범위를 $ log(n) $ 의 효율성으로 구합니다.
최대 n 의 값에 대하여 위의 연산을 수행하기 때문에, $ n * log(\text{len(stages)}) $ 의 효율성을 가집니다.

import bisect
def solution(N, stages):
    answer = []
    stages.sort()
    for i in range(1, N + 1) :
        left = bisect.bisect_left(stages, i)
        right = bisect.bisect_right(stages, i)
        if len(stages) - left == 0: # 1. 찾으려는 원소가 존재하지 않으면
            failuer = (i, 0)        #    실패율은 0
        else:                       # 2. 원소가 존재하면 실패율을 계산해서 출력
            failuer = (i, (right - left) / (len(stages) - left)) 
        answer.append(failuer)
    answer = sorted(answer, key=lambda x: x[1], reverse=True)
    return [x[0] for x in answer]

아래의 소스코드는 N까지 출력해야 되는 조건을 놓치고, 원소 중에 가장 작은 요소까지 출력하여 틀린 케이스입니다. 이 경우로 인하여 시간을 많이 할애했습니다.
1,6,7,9,13,23,24,25 테스트 케이스 실패로 동일한 질문을 한 사람들이 많습니다.

import bisect

def solution(N, stages):
    answer = []
    stages.sort()
    for i in range(1, min(N, stages[-1])+1 ) : 
        left = bisect.bisect_left(stages, i)
        right = bisect.bisect_right(stages, i)
        failuer = (i, (right - left) / (len(stages) - left))
        answer.append(failuer) 
    answer = sorted(answer, key=lambda x: x[1], reverse=True)
    return [x[0] for x in answer]

PREVIOUS[프로그래머스] 올바른 괄호 풀이

NEXT[프로그래머스] 캐시 풀이