문제 설명 및 제한사항
아이디어 및 해결 방법
코드
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
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges