문제

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

나의 코드 (답안참조)

"""
1. 아이디어
fail 이라는 딕셔너리를 만들어 각 스테이지 마다 실패율을 기록한다.
이 문제의 예시로 보면 fail = {1:(1/8), 2:(3/7) 3:(2/4) 4:(1/2) 5:(0/1) } 이다
마지막엔 값을 기준으로 정렬해서 키 값을 반환하도록 한다.

2. 시간복잡도
O(N^2) - 반복문=O(N) * count함수=O(N), 정렬 = O(nlogn)
"""

def solution(N, stages):
    
    fail = {}
    people = len(stages) # 도전한 사람의 수
    
    # 총 문제 수 - n번째 머무른 사람의 수 = n+1번째 도전한 사람의 수
    for stage in range(1, N+1):
        
        if people > 0:
            cnt = stages.count(stage)
            fail[stage] = cnt / people
            people -= cnt
        else:
            # 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
            fail[stage] = 0 
    
    # 딕셔너리에서 value값을 기준으로 내림차순 정렬 후 키 값을 반환한다.
    # 추가설명 : fail는 dictionary이므로 sorted에 fail를 그냥 넘기면 fail의 keys가 들어갑니다. keys는 생략이 가능합니다. 거기에 lambda는 기준을 fail[x]: 즉 value로 정렬한다는 뜻입니다. 그래서 key가 출력되게 됩니다.
    return sorted(fail, key=lambda x : fail[x], reverse=True)

내가 개선한 코드

"""
1. 아이디어
give_up 이라는 리스트를 추가해줌으로서 반복문에서 count를 쓰지 않고 
각 스테이지별로 실패한 사람의 수를 미리 더해준다.

2. 시간복잡도
O(n^2)에서 O(NlogN)으로 개선했다. (마지막 정렬때문에 O(NlogN))
"""

def solution(N, stages):
    
    fail = {}
    people = len(stages)
    give_up = [0] * (N+2) # 각 스테이지별 실패한 사람
    
    for i in stages: # 각 스테이지별로 실패한 사람을 계속 더해준다.
        give_up[i] += 1
        
    for stage in range(1, N+1):
        
        if people > 0:
            fail[stage] = give_up[stage] / people
            people -= give_up[stage]
        else:
            fail[stage] = 0 
    
    return sorted(fail, key=lambda x : fail[x], reverse=True)

느낀점

풀이 방법이 전혀 떠오르지 않아서 답안을 참조했는데 다른 사람의 깔끔하고 작성된 걸 보니 아직 갈 길이 먼 것 같다.

• 시간복잡도가 O(n^2)인게 조금 마음에 걸려서 줄이기 위해 반복문 내에서 count함수를 쓰지 않고 미리 실패한 스테이지를 구해놓는 것으로 바꾸었다. 마지막 sorted함수 때문에 아직 O(nlogn)? 인 것 같은데 그래도 만족한다.

개선 전	개선 후