[프로그래머스 / Level 1] 실패율 (파이썬)

📌문제 설명
슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

실패율은 다음과 같이 정의한다.

스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

📌제한 사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
• 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
• 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

📌 Solution
이번 문제는 level1이지만 level2.25같은 문제랄까? 시간복잡도상으로 제한만 조금 더 있었으면 풀지 못했을 수도 있겠다는 생각을 많이 하였다.

def solution(N, stages): # 실패율 O(n**2)
    answer = []
    fail_list=[]
    dic_list={}
    answer_list=[]
    for i in range(1, N+1):
        full=0
        reach=0
        for j in stages:
            if j >= i:
                full+=1
            if j == i:
                reach+=1
        if full==0:
            dic_list[i]=0
        else:            
            dic_list[i]=reach/full 

    # return dic_list
    
    dict1=sorted(dic_list, key=lambda x : x[1], reverse=True)
    
    for i in dict1:
        answer.append(i[0])

    return answer

생각보다 시간이 빠듯하게 걸리길래 되게 당황한 부분이 많았던 문제였다. 이번 문제는 생각보다 조건에 맞춰서 구현을 하여주면 쉽게 해결은 할 수 있었다. 중간에 dictionary를 활용하여서 정렬만 잘 해주면 해결할 수 있었다.

그러나 위 코드는 시간복잡도상으로 O(n**2)이 되어버리는 문제가 생긴다.
그리하여 시간복잡도를 O(n)으로 만들 필요가 있었다.

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)

위 코드에서와는 달리 애초부터 스테이지에 도달하는지의 대한 여부를 리스트 인덱스를 활용하여서 미리 저장해놓고 나중에 핵심적인 조건을 해결만 해주면 시간을 줄일 수 있었다.

이렇게 문제를 해결하는 도중 sorted 함수에 대해서 보게 되었는데 iterable한 모든 타입에서는 다 사용이 가능하다.

sorted(iterable, key, reverse)
iterable: list, dictionary, tuple, etc...
key: 어떤 조건에 따라 정렬을 시킬지(function)
reverse: 역순으로 정렬을 시킬지

코드에서 보면 key부분에 lambda식이 들어가있는데 spring공부할때도 그렇긴 하였지만 이 lambda식에 대해서는 익숙해져야되겠다는 생각이 되게 많이 들었다.

위 코드에서는 lambda식이 이렇게 작동을 하였다.

1. x라는 파라미터를 받습니다.
2. dic_list[x]를 반환합니다.

여기서 x에 들어가게 되는 것은 바로 앞에 있는 파라미터인 dic_list가 된다.

그리고 기본적으로 dic_list처럼 선언을 하게 되면 key값을 꺼내온다고 한다. 그러므로 x에는 dictionary의 key값들이 들어가게 되는 것이다.

✨ 문제 해결하며 알게 된 점

1. sorted, lambda
2. 시간복잡도 더 생각해보기.