[프로그래머스] 실패율 - 파이썬 Python

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

프로그래머스

 

1. 처음 풀이

def solution(N, stages):
    fail = {}
    for i in range(1, N+1):
        win_cnt, challenge_cnt = 0, 0
        for s in stages:
            if s > i: 
                win_cnt+=1
                challenge_cnt+=1
            elif s == i: 
                challenge_cnt+=1
        if challenge_cnt != 0:
            fail[i] = (challenge_cnt - win_cnt) / challenge_cnt
        else:
            fail[i] = 0
        
    answer = sorted(fail, key=lambda x: (-fail[x], x))       
    return answer

 

제한에 애매하게 통과하길래 다른 풀이를 참고해서 개선할 수 있는지 찾아봤다.

2. 시간 복잡도 개선한 코드

def solution(N, stages):
    # 각 스테이지별 도전자 수를 먼저 계산
    challenge_cnt = [0] * (N + 2)
    for stage in stages:
        challenge_count[stage] += 1 
    
    # 실패율 계산
    total_players = len(stages)
    fail = {}
    for i in range(1, N + 1):
        if total_players == 0:
            fail[i] = 0
        else:
            fail[i] = challenge_cnt[i] / total_players
        total_players -= challenge_cnt[i]
    
    answer = sorted(fail, key=lambda x: (-fail[x], x))
    return answer

 

i. 스테이지 카운팅

• 1번 코드: 각 스테이지마다 모든 플레이어를 순회한다. `O(N*len(stages))`
• 2번 코드: 플레이어를 한 번만 순회하여 각 스테이지의 도전자 수를 계산한다. `O(len(stages))`

ii. 실패율 계산

• 각 스테이지마다 계산하는 점에서 동일하다. `O(N)`

iii. 정렬

• 동일한 정렬 로직을 사용한다. `O(NlongN)`

iv. 최종 시간 복잡도

• 1번 코드: `O(N*len(stages))`
• 2번 코드: `O(len(stages) + N + NlongN)`
• 대규모 입력 시에는 2번 코드가 훨씬 효율적일 것이다. 특히 N과 len(stages)가 모두 큰 경우일수록 2번 코드가 효율적일 것이다.