문제 보기 · Level 1 · 2019 KAKAO BLIND RECRUITMENT · 정답률 63% · 푼 사람 44,243명 (2026-09-30 기준)1
문제
스테이지 N개짜리 게임에서 사용자마다 지금 멈춰 있는 스테이지 번호가 주어진다. N+1은 모든 스테이지를 깬 사용자다. 한 스테이지의 실패율은 (그 스테이지에 머문 사람 수) ÷ (그 스테이지에 도달한 사람 수)다. 실패율이 높은 순으로 스테이지 번호를 돌려준다.
- 1 ≤ N ≤ 500
- stages 길이 최대 200,000
- 실패율이 같으면 번호가 작은 스테이지가 먼저다
- 도달한 사람이 없는 스테이지의 실패율은 0이다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 시간 복잡도로 방법 고르기: 스테이지마다 명단을 다시 세면 느린지 판단한다
- 정렬과 정렬 기준: “실패율 높은 순, 같으면 번호 작은 순”을 key로 만든다
- 조건부 확률: 사용자 한 명을 무작위로 골라 그가 멈춘 스테이지를 \(X\)라 하면, 실패율은 \(P(X = i \mid X \ge i)\)다. 그래서 전체 인원이 아니라 i번에 도달한 사람 수로 나눈다. 도달한 사람이 없으면 조건 \(X \ge i\)의 확률이 0이라 이 값이 정의되지 않는다. 그래서 문제가 0으로 따로 정한다.
1단계 · 작은 예로 손으로 풀기
N = 3, stages = [1, 2, 2, 4] (4는 다 깬 사람)
| 스테이지 | 머문 사람 | 도달한 사람 | 실패율 |
|---|---|---|---|
| 1 | 1명 (1) | 4명 (모두) | 1/4 |
| 2 | 2명 (2, 2) | 3명 (2, 2, 4) | 2/3 |
| 3 | 0명 | 1명 (4) | 0/1 = 0 |
높은 순으로 세우면 2 (2/3), 1 (1/4), 3 (0) → [2, 1, 3].
표를 보면 규칙이 있다. “도달한 사람”은 앞 스테이지에서 도달한 사람에서 앞 스테이지에 머문 사람을 뺀 수다. 4명 → 4 − 1 = 3명 → 3 − 2 = 1명.
2단계 · 가장 단순한 방법과 그 속도
스테이지마다 stages 전체를 훑어 “머문 사람”과 “도달한 사람”을 센다. 스테이지 500개 × 사용자 20만 명 = 1억 번이다. 파이썬에서 10초쯤 걸려 시간 초과가 난다. stages.count(i)를 쓰는 것도 한 줄일 뿐 속에서 20만 번을 도니 똑같다.
3단계 · 핵심 아이디어
여러 번 셀 것은 미리 한 번에 센다.
- stages를 한 번만 훑으며 스테이지마다 머문 사람 수를 표
cnt에 적는다. - 1단계에서 본 규칙으로 도달한 사람 수를 구한다. 처음에는 전원이고, 스테이지를 하나 지날 때마다 그 스테이지에 머문 사람을 뺀다. 둘 다 전체 인원으로 나누면, 머문 사람 수는 “무작위로 고른 사용자가 i번에서 멈출 확률”, 도달한 사람 수는 “i번에 도달할 확률”이 된다. 이 빼기는 확률변수와 분포에서 누적분포함수의 계단 높이가 그 점의 확률이라는 성질과 같다.
- 실패율을 구한 뒤 “실패율 큰 순, 같으면 번호 작은 순”으로 정렬한다.
떠올리는 신호: “같은 목록을 기준만 바꿔 여러 번 센다”면 한 번 훑어 표에 모아 둘 수 있는지 본다.
4단계 · 코드 흐름
- 길이 N + 2짜리 0으로 된 리스트
cnt를 만들고, stages를 돌며cnt[s] += 1. remain(도달한 사람 수)을 전체 인원으로 둔다.- 스테이지 1~N을 차례로 돌며 실패율을 구해 두고,
remain에서 그 스테이지에 머문 사람을 뺀다.remain이 0이면 실패율은 0이다. - 스테이지 번호 1~N을
(-실패율, 번호)기준으로 정렬해 돌려준다.
5단계 · 파이썬 코드
def solution(N, stages):
cnt = [0] * (N + 2) # cnt[s] = s번 스테이지에 머문 사람 수 (N+1은 다 깬 사람)
for s in stages:
cnt[s] += 1
remain = len(stages) # i번 스테이지에 도달한 사람 수
rate = {}
for i in range(1, N + 1):
rate[i] = cnt[i] / remain if remain > 0 else 0
remain -= cnt[i]
return sorted(range(1, N + 1), key=lambda i: (-rate[i], i))
[0] * (N + 2): 0이 N + 2개인 리스트다. 번호 0은 쓰지 않고, 1~N + 1을 쓴다.A if 조건 else B: 도달한 사람이 없을 때 0으로 나누지 않게 막는다.sorted(range(1, N + 1), key=...): 스테이지 번호들을 정렬한다. 비교는 key가 돌려준(-실패율, 번호)로 한다. 실패율에 −를 붙여 큰 실패율이 앞에 오게 하고, 같으면 번호가 작은 것이 앞이다.
6단계 · 실행 추적
N = 5, stages = [2, 1, 2, 6, 2, 4, 3, 3]
cnt: 1번 1명, 2번 3명, 3번 2명, 4번 1명, 5번 0명, 6번(다 깸) 1명
| i | remain (도달) | cnt[i] (머묾) | 실패율 |
|---|---|---|---|
| 1 | 8 | 1 | 1/8 = 0.125 |
| 2 | 7 | 3 | 3/7 ≈ 0.43 |
| 3 | 4 | 2 | 2/4 = 0.5 |
| 4 | 2 | 1 | 1/2 = 0.5 |
| 5 | 1 | 0 | 0/1 = 0 |
정렬: 3 (0.5), 4 (0.5, 번호가 커서 3 뒤), 2, 1, 5 → [3, 4, 2, 1, 5]
7단계 · 복잡도와 흔한 실수
한 번 훑기 \(O(M)\) + 정렬 \(O(N \log N)\)이다. M은 사용자 수다.
- 도달한 사람이 0명인 스테이지에서 0으로 나누면 오류가 난다.
- 실패율이 같은 스테이지의 순서를 빼먹는다. 여기서는 key에 번호를 넣었다. 번호 순
range를 정렬하므로key=lambda i: -rate[i]만 써도 안정 정렬 덕분에 같은 실패율은 번호 순을 지킨다. - 실수 나눗셈 오차가 걱정될 수 있다. 같은 분수(예: 1/2과 2/4)는 나눗셈 결과가 똑같은 실수로 나와서 여기서는 문제가 없다. 더 안전하게 하려면
fractions.Fraction으로 정확한 분수를 쓴다.
Fraction)로 비교하는 느린 풀이와 결과가 같았다 — 05_pg42889_p1.py