프로그래머스 LV1 - 실패율

문제 링크

내 풀이

def solution(N, stages):
    failed_dict = {}
    result = []
    for i in range(1, N+1):
        reach_num = 0
        not_num = 0
        for stage in stages:
            if stage >= i:
                reach_num += 1
                if stage == i:
                    not_num += 1
        if reach_num == 0:
            failed_dict[i] = 0
        else:
            failed_dict[i] = not_num / reach_num
    sorted_dict = sorted(failed_dict.items(), key = lambda item: item[1], reverse=True )
    
    for key, value in sorted_dict:
        result.append(key)
        
    return result

다른 풀이

def solution(N, stages): # 실패율 O(n)
    answer = []
    sum_list=[0]*(N+2)
    dic_list={}
    stages.sort()
    now=len(stages)
    for i in stages:
        sum_list[i]+=1        

    for i in range(1, N+1):
        if now==0:
            dic_list[i] = 0
            continue
        dic_list[i] = sum_list[i]/now
        now-=sum_list[i]
        
    return sorted(dic_list, key=lambda x : dic_list[x], reverse=True)

풀이 해석

stages 정보를 미리 리스트에 저장해놓고 분모는 앞 선 미클리어자수를 빼면서 변화를 주고 dict를 정렬하여 해결하였다.

배울 점

• list에 미리 stages 정보를 저장해두어 시간 복잡도를 줄인 점
• dict정렬 방법