[프로그래머스] 호텔 방 배정

https://school.programmers.co.kr/learn/courses/30/lessons/64063

원하는 호텔방에 손님을 넣되, 그 방이 이미 손님이 있을 경우, 그 방보다 방 번호가 큰 수중 가장 작은 방을 주는 문제다.

유니온파인드를 활용하여 문제를 해결하였음

첫번째 풀이는 전통적인 uf를 활용하되 k의 제한값이 10 **12 이기 때문에 uf = [i for i in range(k+1)]은 시간초과가 걸리므로 dictionary를 활용하였다.

• 여기서 만약, 출제자가 재귀 깊이를 10만 이상 갈 수 있게 테스트케이스를 입력했다면 해당 코드는 틀렸을 듯. 그래서 두번째 정답코드를 고민했다.

from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def solution(k, room_number):
    answer = []
    uf = defaultdict(int)
    
    def find(x):
        if uf[x] == 0:
            uf[x] = x + 1
            return x
        if uf[x] != x:
            uf[x] = find(uf[x])
        return uf[x]

    
    for room in room_number:
        if uf[room] == 0:
            answer.append(room)
            uf[room] = room + 1
        else:
            val = find(room)
            answer.append(val)

    return answer

두번째 코드는 uf를 활용시 재귀가 아닌 while문을 통해 조상을 찾고, 이후에 경로압축을 while 실행하여 재귀를 쓰지않음
이를 통해, recursionlimit를 조절하지 않고도 통과할 수 있었음.

from collections import defaultdict

def solution(k, room_number):
    answer = []
    uf = defaultdict(int)
    
    def find(x):
        # 반복문을 사용하여 부모 노드까지 탐색
        root = x
        while uf[root] != 0:
            root = uf[root]
        
        # 경로 압축
        while x != root:
            parent = uf[x]
            uf[x] = root
            x = parent
            
        return root
    
    for room in room_number:
        if uf[room] == 0:
            answer.append(room)
            uf[room] = room + 1
        else:
            val = find(room)
            answer.append(val)
            uf[val] = val + 1 

    return answer