[프로그래머스/파이썬] 실패율 풀이

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

프로그래머스

 

문제 분석하기

(1) 주어진 입력

• N : 전체 스테이지 개수
• stages : 게임 이용자가 멈춰있는 스테이지 배열

(2) 주어진 조건

• N은 1~500의 자연수
• stages의 length는 1~200,000
• 각 stage 는 1~N+1의 자연수
  • 자연수는 현재 도전중인 스테이지. 즉 이전 스테이지까지 다 깼음을 의미
  • 예를 들어 N+1은 마지막 스테이지(N)까지 클리어한 사용자

 

(3) 구하는 것 : 각 스테이지의 실패율(해당 스테이지에 머무르고 있는 이용자 수 / 해당 스테이지를 깬 이용자 수)을 담은 배열

• 실패율이 높은 스테이지부터 내림차순으로 정렬. (실패율이 같은 경우 낮은 스테이지부터 나오게)

 

일단 풀어보기

먼저 '해당 스테이지에 머무르고 있는 이용자 수'를 구해야 하는데, 단순히 stages를 순회하면서 해당 stage와 일치하는 이용자 수를 구한다면 스테이지의 개수만큼 stages를 돌아야 하므로 이용자 수가 s라면 시간 복잡도가 O(S * N)이 됩니다.

 

그리고 '해당 스테이지를 깬 이용자 수'는 단순히 생각하면 stages를 순회하면서 해당 stage보다 큰 수인 이용자 수를 세어 구할 수 있습니다. 마찬가지로 스테이지의 개수만큼 stages를 돌아야 하므로 O(S * N)의 시간 복잡도를 가집니다.

 

이후, 빈 배열 result에 각 실패율을 스테이지와 함께 (스테이지, 실패율) 의 형태로 추가합니다. (O(N))

 

마지막으로 result를 실패율이 높은 순서(같다면 낮은 스테이지 순서로)로 정렬한 뒤 반환해 마무리합니다. (O(NlogN))

 

최적화하기

우선 '해당 스테이지에 머무르고 있는 이용자 수'를 구하는 것은 계수 정렬이나 해시 테이블을 통해 최적화할 수 있습니다.

특히 최대 / 최소값의 차이가 최대 500이므로 계수 정렬을 사용하는 것이 유효합니다(보통 1,000,000 이하의 차이까지 유효). 계수 정렬을 통해 O(N+K)의 시간 복잡도로 각 스테이지의 이용자 수 배열을 만들고 이를 O(1)의 속도로 접근할 수 있습니다.

# N+1까지 존재하므로 배열의 최댓값은 N+1
# 해당 스테이지에 바로 접근하기 위해 + 1
history = [0] * (n+2)
for stage in stages:
    history[stage] += 1

 

마찬가지로 '해당 스테이지를 깬 이용자 수'도 위에서 구한 각 스테이지 이용자 수 배열을 이용해 더 쉽게 구할 수 있습니다. 배열에서 해당 스테이지 이후부터의 모든 요소의 합이 곧 해당 스테이지를 깬 이용자 수이기 때문이지요. 그런데 이 역시 뒤로 갈수록 합을 구하는 요소 개수가 줄어들지만 해당 배열을 여러 번 순회해야 합니다. 스테이지의 개수는 N, 총 수행 횟수는 N(N+1) / 2이므로 약 O(N^3)의 시간 복잡도가 필요합니다.

ex) 1스테이지를 깬 이용자 수는 2스테이지~N+1스테이지 이용자 수의 합,

2스테이지를 깬 이용자 수는 3스테이지~N+1스테이지의 합...

 

더 빠르게 동작하게 할 수는 없을까요? 새로운 배열에 스테이지 이용자 수 배열의 뒤에서부터 깬 이용자 수를 더해가면서 기록해두면 O(N)으로 각 스테이지를 깬 이용자 수 배열을 만들고 이를 O(1)의 속도로 접근할 수 있습니다. 여기에 배열을 뒤집는데 O(N)이 소요되지만 총 시간 복잡도는 O(N)가 됩니다.

reverse_history = history[::-1]
clears = [0] * (n+1)
prev = 0
for i in range(len(reverse_history)):
    prev += reverse_history[i]
    clears[-i] = prev

 

그리고 일단 풀어볼 때 고려하지 않았던 사항 중에 '해당 스테이지를 깬 이용자 수'가 없을 때에 대한 고려도 해야 합니다. 수를 0으로 나누게 되면 ZeroDivisionError이 발생하고 맙니다. 그래서 이 경우에는 실패율을 원래 계산식을 사용하는 대신 0을 할당해야 합니다.

failures = []
for i in range(1, n+1):
    if clears[i] == 0:
        failures.append((i, 0))
    else:
        failures.append((i,history[i] / clears[i]))

 

이후 이 두 값을 통해 실패율을 구해 정렬한 뒤, 스테이지 번호들만 반환하면 되는데, 여기서는 특별히 최적화할 방법을 찾지는 못했습니다. 다만 코드를 간결하게 하기 위해 리스트 컴프리헨션을 수행한 뒤 반환했습니다.

return [x[0] for x in sorted(failures, key = lambda x : (-x[1], x[0]))]

 

정답을 맞춘 전체 코드는 다음과 같습니다.

def solution(n, stages):
    history = [0] * (n+2)
    for stage in stages:
        history[stage] += 1

    reverse_history = history[::-1]
    clears = [0] * (n+1)
    prev = 0
    for i in range(len(reverse_history)):
        prev += reverse_history[i]
        clears[-i] = prev

    failures = []
    for i in range(1, n+1):
        if clears[i] == 0:
            failures.append((i, 0))
        else:
            failures.append((i, history[i] / clears[i]))
    
    return [x[0] for x in sorted(failures, key = lambda x : (-x[1], x[0]))]

 

 

향후 개선

위의 코드로 정답을 맞은 뒤, 인터넷을 찾아보며 다른 사람들의 풀이를 뒤져보았습니다. 저처럼 계수 정렬을 쓰지는 않았지만 Collections 모듈의 count 메서드로 해당 스테이지를 머무르고 있는 이용자 수를, len(stages)를 통해 해당 스테이지를 클리어한 이용자 수를 구해 실패율을 구하고 있었습니다. count 메서드를 사용하는 것보다는 계수 정렬이 나은 것 같지만, 실패율을 구하는 데 있어서는 원래의 len(stages)에서 해당 스테이지를 머무르고 있는 이용자 수를 빼주고 다음 스테이지가 이용하는 형태가 더 효율적인 듯했습니다.

 

그래서 이를 반영해 개선한 코드는 다음과 같습니다.

def solution(n, stages):
    history = [0] * (n+2)
    for stage in stages:
        history[stage] += 1

    total_player = len(stages)

    failures = []
    for i in range(1, n+1):
        if total_player == 0:
            failures.append((i, 0))
        else:
            failures.append((i, history[i] / total_player))
            total_player -= history[i]
    
    return [x[0] for x in sorted(failures, key = lambda x : (-x[1], x[0]))]