[문제 풀이] 실패율

 

코딩테스트 연습 - 실패율

해결 과정

python의 Counter를 사용하여 미리 개수를 저장해두고 푼 풀이.

리팩토링 할 때는 다른 풀이를 보고 successPlayersCount를 추가적으로 뒀다. (이런 아이디어 배우자)

 

나의 풀이

# 리팩토링 - successPlayersCount를 두고 빼주는 아이디어.
# 테스트 22 〉	통과 (12.03ms, 18.3MB)
from collections import Counter

def solution(N, stages):
    counter = Counter(stages)
    failureRates = [] # (번호, 비율)
    successPlayersCount = len(stages)
    for i in range(1, N+1):
        if successPlayersCount == 0:
            failureRates.append((i, 0))
        else:
            failureRates.append((i, counter[i] / successPlayersCount))
            successPlayersCount -= counter[i]
        
    return [x[0] for x in sorted(failureRates, key= lambda x: x[1], reverse=True)]

print(solution(5, [2, 1, 2, 6, 2, 4, 3, 3]))

 

# 처음 코드
# 테스트 22 〉	통과 (24.17ms, 18.4MB)
from collections import Counter

def solution(N, stages):
    counter = Counter(stages)
    failureRates = [] # (번호, 비율)

    for i in range(1, N+1):
        temp = 0
        for key, value in counter.items():
            if key >= i:
                temp += value
        if temp == 0:
            failureRates.append((i, 0))
        else:
            failureRates.append((i, counter[i] / temp)) 
    
    failureRates.sort(key= lambda x: x[1], reverse=True)
    return [x[0] for x in failureRates]

print(solution(5, [2, 1, 2, 6, 2, 4, 3, 3]))

 

다른 풀이

제일 상단에 있는 풀이였다. denomiator로 개수를 세주는 IDEA와 맨 마지막 return에서 dictionary의 key만 빼주는 방법을 처음 알게 됐다. 다만 이 풀이는 시간이 너무 오래 걸리는 풀이이다. list.count()는 O(n)의 시간을 갖기 때문에 전체적으로 O(n^2)의 시간이 걸린다.

def solution(N, stages):
    result = {}
    denominator = len(stages)
    for stage in range(1, N+1):
        if denominator != 0:
            count = stages.count(stage)
            result[stage] = count / denominator
            denominator -= count
        else:
            result[stage] = 0
    return sorted(result, key=lambda x : result[x], reverse=True)

 

IDEA