[Python] 프로그래머스 Lv.1 실패율

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

프로그래머스

 

실패율 : 실패자/스테이지 도달자
N : 전체 스테이지 수
stages : 사용자가 있는 스테이지의 번호 담긴 배열
실패율이 높은 스테이지부터 내림차순 return

 

1부터 N까지를 순회하여, (stage에 있는 i번째 수의 개수/남은 사람의 수)가 실패율을 반환한다는 원리를 금방 이해했다.

 

그래서 마찬가지로 순회한 다음, 그 실패율을 담은 배열의 순위를 return 값으로 잡는 것이 목표이므로 아래와 같이 코드를 짰다.

def solution(N, stages):
    answer = []
    a = len(stages)
    for i in range(1, N+1):
        count_i = stages.count(i)
        if a == 0:
            answer.append(0)
        else:
            answer.append(count_i / a)
        a -= count_i
        
    result = sorted(range(len(answer)), key=lambda i: (-answer[i], i))
    return [idx + 1 for idx in result]

 

정답에는 성공했는데, 상당히 많은 시간을 소요해서 마음에 들지 않았고.. 자료구조를 통한 해결책을 구상하였다.

그러나 해결책을 찾진 못했고.. 대신 다른 사람의 풀이를 보다가 대단한 코드를 발견했다.

아래 식을 통해 정말 말도 안 되는 속도의 비결을 알 수 있었다.

 

from collections import Counter
from collections import deque

def solution(N, stages):
    # backup = deepcopy(stages)
    tmpAnswer = []

    sub = len(stages)
    result = Counter(stages)
    result = list(result.items())
    result.sort(key=lambda x: x[0])

    for data in result:
        currPosPlayer = data[1]
        if(data[0]== N+1): # 마지막스테이지 통과한사람이면
            continue
        tmpAnswer.append([data[0], currPosPlayer / sub])
        sub -= currPosPlayer

    # tmpAnswer.sort(key=lambda x: x[1], reverse=True)
    tmpAnswerDict = dict(tmpAnswer)
    dq = deque()

    for i in range(1, N + 1):
        data = tmpAnswerDict.get(i)
        if data == None:
            dq.append([i, 0])
            continue
        dq.append([i, data])
    resultAnswer = list(dq)

    resultAnswer.sort(key=lambda x: x[1], reverse=True)

    answer = []
    for i in range(N):
        answer.append(resultAnswer[i][0])
    return answer

 

 

시간복잡도가 거의 100배 짧아졌음을 문제풀이속도를 통해 확인할 수 있었다.

 

도대체 이 말도 안 되는 차이의 비결은 무엇인가?

1. Counter 클래스를 사용하여 각 스테이지에 도달한 플레이어 수를 쉽게 계산한다. Counter 클래스는 입력된 리스트나 문자열의 요소들의 개수를 세어주는 객체다. 이를 통해 각 스테이지의 플레이어 수를 세고, 결과를 딕셔너리 형태로 반환한다.
2. Counter 클래스를 이용하여 계산한 결과를 리스트로 변환하고, 스테이지 번호를 기준으로 정렬한다. 이는 각 스테이지의 플레이어 수를 계산하는데 O(n)의 시간 복잡도를 가진다. 반면 stage.count(i)는 리스트를 선형으로 탐색하여 해당 스테이지의 개수를 세는 연산을 수행하게 되는데, 이는 각 스테이지마다 모든 리스트 요소를 탐색해야 하므로 시간복잡도가 O(N^2)가 될 수 있다.
3. deque는 양쪽 끝에서의 삽입과 삭제가 O(1)의 시간복잡도를 가지는 반면, 리스트의 경우에는 양쪽 끝에서의 삽입과 삭제가 O(n)의 시간복잡도를 가지기 때문에 매우 큰 리스트의 경우에는 deque가 약간 더 빠를 수 있다.
4. 내장 모듈 collections의 deque는 이중 연결 리스트로 구현되어 있어 삽입과 삭제가 효율적으로 이루어진다. 따라서 데이터 삽입을 지속적으로 해야 하는 이 문제에서는 deque를 사용하는 것이 적절하다.

비결의 가장 큰 점은 역시 딕셔너리 형태이다. {스테이지, 스테이지 탈락자 수} 형태로 만들어져 있기 때문에 위에서 짠 코드보다도 직관적으로 인지할 수 있다. 또한 기존에 썼던 코드에서 count가 가져다 줄 시간복잡도에 대해 제대로 인지하지 못했다. 어떠한 알고리즘으로 돌아가는지를 연습을 통해 더 익숙해져야겠다는 생각이 들었다. count를 썼기에 코드 줄 자체는 훨씬 짧으나, 시간을 줄이기 위해서는 복잡한 코드라도 익숙해져야 한다.