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