프로그래머스

프로그래머스 호텔 방 배정 풀이: 연속 점유 구간을 합치는 유니온 파인드

2026년 10월 23일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 호텔 방 배정
출처: 프로그래머스, 2019 카카오 개발자 겨울 인턴십
학습: 유니온 파인드 학습 가이드
자체 판단 난이도: Level 3

이미 찬 방에서 다음 빈 방을 찾는 과정을 반복 검색으로 처리하면 같은 구간을 계속 훑게 된다. 점유된 연속 구간을 Union-Find로 묶고 오른쪽 끝을 저장하면 이 검색을 빠르게 건너뛸 수 있다. 표준 자료구조를 문제에 맞게 확장하는 것이 핵심이므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 변경될 수 있으므로 제출 전에 공식 문제 페이지를 다시 확인한다.

1. 문제 요약

호텔 방은 1번부터 k번까지 있고 처음에는 모두 비어 있다. 고객이 원하는 방이 비어 있으면 그 방을 배정하고, 이미 사용 중이면 그보다 큰 번호 중 가장 먼저 나오는 빈 방을 배정한다. 고객 요청 순서대로 배정된 방 번호를 반환한다.

제한에서 눈여겨볼 값은 방 개수 k가 최대 10^12라는 점이다. 반면 요청 수는 최대 200,000개다. 따라서 k개의 칸을 가진 배열로 점유 여부를 저장할 수는 없고, 실제로 배정된 방만 기록해야 한다.

예제 요청 [1, 3, 4, 1, 3, 1]의 결과는 [1, 3, 4, 2, 5, 6]이다. 네 번째 요청에서 1번 방의 오른쪽으로 연속해서 찬 구간은 아직 없으므로 2번을 배정한다. 이후 1번부터 5번까지 차면 다음 요청은 그 구간의 오른쪽 끝 다음인 6번으로 바로 이동해야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

배정된 방의 연속 구간을 하나의 집합으로 본다

parent에는 실제로 배정된 방만 넣는다. Union-Find의 한 집합은 번호가 서로 이어진 최대 연속 점유 구간 하나를 나타낸다. 각 집합의 대표에는 그 구간에서 가장 큰 방 번호인 rightmost를 함께 저장한다.

요청한 방이 parent에 없으면 비어 있으므로 그대로 배정한다. 이미 배정된 방이면 find로 그 방이 속한 구간의 대표를 찾고, rightmost[root] + 1을 배정한다. 요청 방부터 구간의 오른쪽 끝까지는 모두 차 있으므로, 그 다음 번호가 가장 가까운 빈 방이다.

새 방을 배정할 때 왼쪽과 오른쪽 구간을 합친다

새 방 room을 배정하면 우선 자기 자신만 포함하는 집합으로 만든다. room - 1이나 room + 1이 이미 배정되어 있다면 새 방과 이웃 구간을 Union-Find로 합친다. 합친 대표의 rightmost에는 두 구간의 오른쪽 끝 중 큰 값을 보관한다.

배정 전: [1, 2]가 점유됨   [4, 5]가 점유됨
3번 배정 후: [1, 2, 3, 4, 5]가 하나의 구간으로 합쳐짐
대표의 rightmost: 5
다음 빈 방: rightmost + 1 = 6

union은 트리 크기가 작은 쪽을 큰 쪽에 붙이고, find는 경로 압축을 한다. 두 최적화를 함께 사용하므로 집합을 합치고 대표를 찾는 연산은 분할 상환 O(α(q))이다. 여기서 q는 요청 수다.

공식 예제의 구간이 어떻게 변하는가

집합의 대표 자체가 오른쪽 끝일 필요는 없다. 트리 균형을 위해 대표는 크기 기준으로 선택하고, rightmost에 구간 끝을 별도로 기록한다.

요청	배정	처리 후 점유 구간	다음 빈 방을 찾는 기준
1	1	`[1, 1]`, `[3, 3]`	1번 구간 끝은 1
3	3	`[1, 1]`, `[3, 3]`	3번 구간 끝은 3
4	4	`[1, 1]`, `[3, 4]`	3번과 4번을 합쳐 끝은 4
1	2	`[1, 4]`	2번이 1번·3번과 이어져 끝은 4
3	5	`[1, 5]`	기존 구간 끝 4 다음인 5를 배정
1	6	`[1, 6]`	기존 구간 끝 5 다음인 6을 배정

네 번째 요청이 2번 방을 채울 때 1번 집합과 3~4번 집합이 함께 합쳐진다. 이후에는 1번이나 3번을 다시 요청해도 같은 구간 대표로 이동해 바로 5번, 6번을 찾는다.

왜 방 번호 전체를 저장하거나 매번 앞에서부터 찾지 않는가

k가 10^12까지라면 occupied = [False] * (k + 1) 방식은 입력을 읽기 전부터 메모리를 감당할 수 없다. 반대로 딕셔너리와 DSU는 실제 배정된 최대 q개의 방만 저장한다.

이미 찬 요청 방에서 while candidate in occupied: candidate += 1로 하나씩 찾는 방법은 [1, 1, 1, ...] 요청에서 앞선 구간을 매번 다시 읽는다. 방을 q개 배정할 때 검사 횟수가 1 + 2 + ... + q까지 늘어 O(q^2)가 될 수 있다. DSU는 점유 구간을 합쳐 두어 이 반복 탐색을 건너뛴다.

시간·공간 복잡도

요청 수를 q라고 하자. 각 요청은 대표 검색을 하고, 새 방은 왼쪽·오른쪽 이웃과 최대 두 번 합친다. 경로 압축과 크기 기준 합치기를 사용하므로 전체 시간 복잡도는 분할 상환 O(q α(q))이며, 딕셔너리 연산은 평균 O(1)로 본다.

배열은 방 번호 k개가 아니라 실제 배정된 방마다만 만들므로 공간 복잡도는 O(q)다. 함수의 k는 방 번호의 상한이지만, 입력은 항상 배정 가능한 경우로 보장되므로 k 크기의 구조를 만들 필요가 없다.

3. 문제 해결 코드 (Python)

find는 반복문 두 번으로 루트를 찾은 뒤 지나온 부모를 모두 압축한다. 재귀를 쓰지 않으므로 요청이 길게 이어져도 Python 호출 깊이에 기대지 않는다. 합칠 때는 작은 집합을 큰 집합에 붙이고, 새 대표에만 크기와 오른쪽 끝 정보를 남긴다.

def solution(k, room_number):
    parent = {}
    size = {}
    rightmost = {}

    def find(room):
        root = room
        while parent[root] != root:
            root = parent[root]

        while room != root:
            next_room = parent[room]
            parent[room] = root
            room = next_room

        return root

    def union(room_a, room_b):
        root_a = find(room_a)
        root_b = find(room_b)

        if root_a == root_b:
            return root_a

        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a

        parent[root_b] = root_a
        size[root_a] += size[root_b]
        rightmost[root_a] = max(rightmost[root_a], rightmost[root_b])
        del size[root_b]
        del rightmost[root_b]
        return root_a

    answer = []

    for requested in room_number:
        if requested in parent:
            root = find(requested)
            assigned = rightmost[root] + 1
        else:
            assigned = requested

        parent[assigned] = assigned
        size[assigned] = 1
        rightmost[assigned] = assigned

        if assigned - 1 in parent:
            union(assigned, assigned - 1)
        if assigned + 1 in parent:
            union(assigned, assigned + 1)

        answer.append(assigned)

    return answer

parent에 방이 존재하는지는 그 방이 이미 배정됐는지 판별하는 데도 쓰인다. rightmost는 루트 키만 유지하므로 조회할 때는 반드시 find(requested) 결과를 사용한다.

복사해 실행할 테스트

assert solution(10, [1, 3, 4, 1, 3, 1]) == [1, 3, 4, 2, 5, 6]
assert solution(5, [2, 4, 2, 3]) == [2, 4, 3, 5]
assert solution(3, [1, 1, 1]) == [1, 2, 3]
assert solution(10**12, [10**12 - 1, 10**12 - 1]) == [10**12 - 1, 10**12]

large = solution(200_000, [1] * 200_000)
assert large == list(range(1, 200_001))

4. 공식 예제와 추가 검증

공식 예제, 서로 떨어진 점유 구간을 새 방으로 잇는 경우, 가장 큰 방 번호 경계, 최대 요청 수를 실행해 확인했다.

공식 예제

입력: k = 10, room_number = [1, 3, 4, 1, 3, 1]
기대 출력: [1, 3, 4, 2, 5, 6]
실행 결과: 통과
검증 목적: 구간 병합 뒤 반복 요청이 오른쪽 첫 빈 방으로 건너뛰는지 확인

추가 검증 1: 두 점유 구간 사이를 채우기

입력: k = 5, room_number = [2, 4, 2, 3]
기대 출력: [2, 4, 3, 5]
실행 결과: 통과
검증 목적: 3번 방이 두 구간을 연결할 때 대표의 오른쪽 끝도 갱신되는지 확인

추가 검증 2: 최대 방 번호 부근

입력: k = 10^12, room_number = [10^12 - 1, 10^12 - 1]
기대 출력: [10^12 - 1, 10^12]
실행 결과: 통과
검증 목적: 거대한 k를 배열 인덱스로 쓰지 않고 상한 근처 방을 배정하는지 확인

추가 검증 3: 최대 요청 수에서 같은 방 반복

입력: k = 200,000, room_number = [1]이 200,000회 반복
기대 출력: [1, 2, 3, ..., 200,000]
실행 결과: 통과
검증 목적: 긴 점유 구간을 매 요청마다 선형 탐색하지 않는지 확인

5. 다른 풀이 방식 검색 및 비교

프로그래머스 호텔 방 배정 공식 문제는 이미 배정된 요청이 들어오면 그보다 큰 첫 빈 방을 선택하도록 정의한다.
Kwon의 호텔 방 배정 풀이는 배정된 방에서 다음 빈 방으로 이어지는 successor 포인터를 저장하고 경로를 압축하는 접근을 소개한다.

successor 포인터만 저장하는 방법은 구현이 짧고, 이미 찬 번호에서 다음 후보로 이동하는 흐름이 직접 드러난다. 이 글은 대신 인접한 점유 방들을 집합으로 묶고 rightmost 메타데이터를 둔다. 그 결과 일반 Union-Find의 크기 기준 합치기와 경로 압축을 그대로 적용하면서, 집합 대표가 가장 오른쪽 방이 아닐 수 있다는 점을 별도 정보로 처리한다.

마무리

이 문제에서 필요한 것은 전체 호텔 상태가 아니라 실제로 점유된 방들의 연속 구간이다. 새 방을 배정할 때 양옆의 점유 구간을 합치고, 각 집합의 오른쪽 끝을 저장하면 요청 방에서 다음 빈 방까지 반복해서 훑지 않아도 된다. k가 커도 메모리는 요청 수에 비례한다.