title: "[프로그래머스] 호텔 방 배정 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/64063"
description: "프로그래머스 Level 4 문제 [호텔 방 배정]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import sys; sys.setrecursionlimit(1000000)
from collections import defaultdict

# 방 숫자의 범위가 10^12로 너무 큽니다.
# parent 배열 대신 parent dictionary를 활용하여
# 불필요한 메모리 사용을 줄입니다.
# rank도 마찬가지입니다.
p = dict()
rank = dict()
    
def find(x):
    if p.get(x, x) == x:
        return x
    p[x] = find(p[x])
    return p[x]

def merge(x, y):
    x = find(x)
    y = find(y)
    p[x] = y
        
def solution(k, room_number):
    # 각각의 방을 원소로 하는 Union-find로 해결합니다.
    # 처음에는 각 방은 자기 자신을 대표로 하는 집합입니다.
    # 어떤 방이 차면, 자기 다음 방(이 속한 집합)에 합쳐집니다.
    answer = []
    for roomnum in room_number:
        hit = find(roomnum)
        answer.append(hit)
        merge(hit, hit+1)
        
    return answer

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges