문제19 - 호텔 방 배정 (Python)

프로그래머스

방 개수가 최대 $ 10^{12} $개에 달하는 상황에서 고객의 요구에 따라 빈 방을 효율적으로 찾아 배정하는 문제입니다. 대규모 데이터셋을 처리하기 위한 자료구조 선택과 탐색 시간을 단축하는 경로 압축(Path Compression) 기법이 핵심입니다.

---

1.  나의 풀이

배정된 방의 정보를 동적으로 관리하기 위해 딕셔너리를 사용했습니다. 재귀 호출을 통해 빈 방을 찾고, 돌아오는 과정에서 거쳐온 모든 방의 이정표를 갱신하여 탐색 효율을 극대화했습니다.

import sys

# 재귀 한계를 충분히 늘려 런타임 에러를 방지합니다.
sys.setrecursionlimit(10 ** 6)

def book(room_dict, want_no, k):
    # 원하는 방이 아직 배정되지 않은 경우 (빈 방 발견)
    if want_no not in room_dict:
        # 현재 방을 배정하고 다음 비어있을 가능성이 높은 방을 가리키게 합니다.
        room_dict[want_no] = want_no + 1
        return want_no
    
    # 이미 배정된 방이라면 이정표를 따라 다음 빈 방을 재귀적으로 탐색합니다.
    booked_room = book(room_dict, room_dict[want_no], k)
    
    # 경로 압축: 탐색 과정에서 거쳐온 방들의 이정표를 최종 빈 방의 다음 번호로 갱신합니다.
    room_dict[want_no] = booked_room + 1
    return booked_room

def solution(k, room_number):
    # 전체 방을 미리 생성하지 않고 배정된 방만 관리합니다.
    room_dict = dict()
    answer = [0] * len(room_number)
    
    for idx, want_no in enumerate(room_number):
        answer[idx] = book(room_dict, want_no, k)

    return answer

 

---

2.  오늘 배운 점 및 복기 노트

효율성 테스트 미달 코드 분석

최초에는 다음과 같이 전체 방 개수만큼 배열을 선언하거나, 모든 방 번호를 키로 갖는 딕셔너리를 미리 생성하여 접근했습니다.

# 실패 사례 1: 배열 선언 (메모리 초과)
def solution(k, room_number):
    rooms = [0] * (k + 1) # k가 1조일 경우 메모리 할당 불가
    # ... 후략 ...

# 실패 사례 2: 딕셔너리 사전 생성 (메모리 및 시간 초과)
def solution(k, room_number):
    room_nos = [i for i in range(0, k + 2)]
    prev_next_idx = [[0, j - 2, j] for j in range(1, k + 3)]
    room_dict = dict(zip(room_nos, prev_next_idx)) # 초기화 과정에서 이미 제한 초과
    # ... 후략 ...

위 코드들은 \( k = 10^{12} \)라는 제한 사항을 간과했습니다. 파이썬에서 이 정도 규모의 리스트를 생성하는 것은 불가능하며, 공간 복잡도가 메모리 한계를 아득히 초과하게 됩니다.

 

데이터 규모에 따른 사고의 전환

입력값의 최대 범위가 극단적으로 큰 경우, 전체 공간을 물리적으로 확보하는 것이 아니라 필요한 데이터만을 담을 수 있는 유연한 자료구조가 필요합니다. 딕셔너리는 해시 맵 구조를 통해 존재하지 않는 방 번호에 대해 공간을 낭비하지 않으므로 이 문제의 유일한 해답이 됩니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

희소 행렬(Sparse Matrix) 사고

문제에서 방 개수 $k$가 $10^{12}$라는 강력한 힌트를 줍니다.

• 배열($O(1)$ 접근)의 포기: 파이썬에서 $10^{12}$ 크기의 리스트를 선언하는 것은 불가능합니다. 공간 복잡도가 메모리 한계를 아득히 초과하기 때문입니다.
• 희소 행렬(Sparse Matrix) 사고: 실제로 예약이 들어오는 방 번호는 최대 20만 개($N$)뿐입니다. 즉, 1조 개의 방 중에서 우리가 관심을 가질 방은 극히 일부입니다.
• 해시 맵(Dictionary)의 필연성: 존재하지 않는 방 번호에 대해 공간을 낭비하지 않으면서, 예약된 방만 쏙쏙 골라 관리할 수 있는 딕셔너리가 유일한 해답이 됩니다.

Lesson: "입력값의 최대 범위($k$)가 너무 크다면, 전체 공간을 만드는 것이 아니라 필요한 데이터($N$)만 담을 수 있는 유연한 자료구조를 선택해야 합니다."

 

경로 압축(Path Compression)을 통한 탐색 혁신

단순히 방이 찼을 때 \( +1 \)씩 전진하며 선형 탐색을 수행하면 \( O(N^2) \)의 시간 복잡도가 발생하여 효율성 테스트에서 탈락합니다. 재귀를 통해 빈 방을 찾은 후, 돌아오면서 거쳐온 모든 방의 값을 '찾아낸 빈 방의 다음 번호'로 업데이트하는 경로 압축 기법은 탐색 시간을 획기적으로 단축합니다. 이는 Union-Find 자료구조의 핵심 원리와 동일합니다.

 

언어의 한계를 넘는 코드 설계 (재귀 vs 반복문)

파이썬의 재귀 깊이 제한(기본 1,000회)은 실전에서 큰 변수가 됩니다. sys.setrecursionlimit으로 제한을 늘려 해결할 수 있지만, 스택 오버플로의 위험을 완전히 제거하려면 반복문을 이용한 경로 압축 테크닉도 숙지해야 합니다.

# 반복문 기반 경로 압축 예시
visit = [n]
while n in room_dic:
    n = room_dic[n]
    visit.append(n)
    
# 찾아낸 빈 방 n의 다음 번호로 지나온 모든 이정표를 일괄 업데이트
for j in visit: 
    room_dic[j] = n + 1

 

환경 최적화와 안정성 확보

Level 4 수준의 고난도 문제에서는 알고리즘의 정교함뿐만 아니라 언어적 특성에 따른 환경 설정도 점수에 직결됩니다. 재귀 깊이 체크와 반복문 변환 가능성을 동시에 고려하는 습관이 중요합니다.