문제 보기 · Level 4 · 2019 카카오 개발자 겨울 인턴십 · 정답률 36% · 푼 사람 5,316명 (2026-09-30 기준)1

문제

호텔에 1 ~ k번 방이 있다. 손님이 차례로 원하는 방 번호를 낸다. 그 방이 비었으면 준다. 찼으면 그보다 번호가 크면서 비어 있는 방 중 가장 작은 방을 준다. 손님마다 받은 방 번호를 돌려준다.

  • 1 ≤ k ≤ 10¹²
  • 손님 1 ~ 200,000명, 모두 방을 받을 수 있는 경우만 주어진다

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 유니온 파인드: “찬 방은 다음 빈 방을 가리킨다”는 줄을 만들고, 따라갈 때 지나온 방들이 빈 방을 바로 가리키게 줄인다(경로 압축).
  • 딕셔너리와 집합: k가 10¹²이라 리스트를 만들 수 없다. 찬 방만 딕셔너리에 적는다.
  • 동치관계와 분할: 같은 빈 방에 닿는 방들을 한 무리로 본다. 한 무리는 빈 방 하나와 그 바로 아래로 줄지어 찬 방들이다. 무리의 빈 방을 내주면 그 무리 전체가 바로 위 무리에 합쳐진다.
1단계 · 작은 예로 손으로 풀기

원하는 방 [1, 3, 4, 1, 3, 1]

  • 1, 3, 4는 비어 있어 그대로 준다.
  • 넷째 손님은 1: 찼다 → 2가 비어 있다 → 2.
  • 다섯째 손님은 3: 3, 4가 찼다 → 5.
  • 여섯째 손님은 1: 1, 2, 3, 4, 5가 찼다 → 6.

답은 [1, 3, 4, 2, 5, 6]이다. 마지막 손님은 다섯 방을 하나씩 넘어갔다. 같은 방을 원하는 손님이 계속 오면 넘어가는 방이 점점 늘어난다.

2단계 · 가장 단순한 방법과 그 속도

원하는 방부터 하나씩 올라가며 빈 방을 찾으면, 모두 1번을 원할 때 i번째 손님이 i − 1개 방을 넘는다. 20만 명이면 약 200억 번이다.

3단계 · 핵심 아이디어
  • 찬 방은 다음을 가리킨다: 방 r을 주면 nxt[r] = r + 1로 적는다. “r이 찼으니 r + 1부터 알아보라”는 뜻이다. 빈 방은 딕셔너리에 없다.
  • 따라가기: 원하는 방에서 nxt를 따라가다 딕셔너리에 없는 방에 닿으면 그 방이 빈 방이다. 이것은 유니온 파인드의 find와 같다. 빈 방이 대표다.
  • 경로 압축: 따라가며 지나온 방들의 nxt를 찾은 빈 방으로 바꿔 둔다. 다음에 같은 길을 오는 손님은 한 번에 건너뛴다.
4단계 · 코드 흐름
  1. 빈 딕셔너리 nxt를 만든다.
  2. 손님마다: find(원하는 방)으로 빈 방 r을 찾고, 답에 적고, nxt[r] = r + 1.
  3. find(x): x가 nxt에 있는 동안 따라가며 지나온 방을 모은다. 닿은 방을 지나온 방들의 nxt로 적고 돌려준다.
5단계 · 파이썬 코드 
def solution(k, room_number):
    nxt = {}                                  # nxt[x]: x가 찼으면 다음에 알아볼 방

    def find(x):
        path = []
        while x in nxt:                       # 빈 방이 나올 때까지
            path.append(x)
            x = nxt[x]
        for p in path:                        # 경로 압축
            nxt[p] = x
        return x

    answer = []
    for want in room_number:
        r = find(want)
        answer.append(r)
        nxt[r] = r + 1
    return answer
  • find를 재귀로 짜면 같은 방을 원하는 손님이 20만 명일 때 깊이가 커져 RecursionError가 날 수 있다. 지나온 방을 리스트에 모았다가 한꺼번에 고친다.
  • k는 코드에서 쓰지 않는다. 모든 손님이 방을 받는다고 문제가 보장한다.
6단계 · 실행 추적

원하는 방 [1, 3, 4, 1, 3, 1]

원하는 방 따라간 길 받은 방 바뀐 뒤 nxt
1 1 1 {1: 2}
3 3 3 {1: 2, 3: 4}
4 4 4 {1: 2, 3: 4, 4: 5}
1 1 → 2 2 {1: 2, 2: 3, 3: 4, 4: 5}
3 3 → 4 → 5 5 {1: 2, 2: 3, 3: 5, 4: 5, 5: 6}
1 1 → 2 → 3 → 5 → 6 6 {1: 6, 2: 6, 3: 6, 4: 5, 5: 6, 6: 7}

다섯째 손님 때 3이 5를 바로 가리키게 줄어서, 여섯째 손님은 4를 거치지 않는다. 마지막 줄에서 1, 2, 3이 모두 6을 가리키게 줄었다.

7단계 · 복잡도와 흔한 실수

경로 압축 덕분에 한 번 걸은 긴 길을 다시 걷지 않는다. 20만 명이 모두 1번을 원하는 경우와 무작위 경우로 재 보니 합쳐서 1초 남짓이었다.

  • k 크기의 리스트를 만들어 메모리가 넘친다.
  • 경로 압축 없이 따라가 효율성에서 시간 초과가 난다.
  • 재귀 find로 깊이가 깊어져 RecursionError가 난다.
검증: 문제의 예시를 통과했고, 6단계 표의 nxt 변화를 코드로 확인했다. 무작위 입력 3,000개에서 “원하는 방부터 하나씩 올라가며 빈 방을 찾는” 풀이와 결과가 같았다. 손님 20만 명의 시간도 쟀다 — 15_pg64063_p1.py

  1. 프로그래머스 스쿨, “호텔 방 배정” (https://school.programmers.co.kr/learn/courses/30/lessons/64063), 2026-09-30 조회. ↩