알고리즘 개요
- 스테이지 별 실패율이 가장 높은 순으로 배열의 형태로 결과 값을 내보낸다.
- N: 전체 스테이지 수
- stages: 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열
- N + 1 은 마지막 스테이지 (N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
- 실패율이 같은 경우, 스테이지가 낮은 값이 좀 더 앞에 나와야 한다.
실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
예시
- N: 5
- stages: [2, 1, 2, 6, 2, 4, 3, 3]
- 결과값: [3,4,2,1,5]
스테이지 1 실패율: 1 / 8
스테이지 2 실패율: 2 / 7
스테이지 3 실패율: 3 / 5
스테이지 4 실패율: 1 / 2
스테이지 5 실패율: 0 / 1
풀이
def solution(N, stages):
length = len(stages)
result = {}
for n in range(1, N + 1):
if n in stages:
ct = stages.count(n)
result[n] = ct / length
length -= ct
else:
result[n] = 0
return [r[0] for r in sorted(result.items(), key = lambda item: item[1], reverse=True)]- for문으로 stage 1부터 마지막 스테이지 N까지 실패율을 계산하여 result 객체에
스테이지: 실패율형태로 값을 담는다. 이후에 set 형태의 값을 담은 list로 변환 되기 때문에 set 형태로 list에 append 해놓아도 괜찮다. - length는 실패율을 계산할 때마다 스테이지에 도달한 플레이어 수가 줄어들어 실패율을 계산한 후, 다음 스테이지 실패율을 계산하기 위해 전 스테이지 도달 플레이어 수 만큼 줄인다.
- 만약 stages 배열에 스테이지 해당 번호가 없는 경우에는 해당 스테이지의 실패율은 0이다.
- key 매개 변수로 비교할 값을 실패율로 설정한다.
- key 값을 reverse = True로 내림차순으로 설정한다.
- 실패율이 같은 경우, key 값이 아닌 item[0]은 오름차순으로 자동 정렬된다.
- list comprehension을 통해 item[1] 값만 정렬된 배열을 리턴한다.
