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

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

프로그래머스

 

🤔 문제분석

유니온-파인드(서로소 집합) 으로 문제를 접근하면 된다.

k개의 수가 매우 크기때문에 기존 리스트를 사용한 접근 방식 대신에 딕셔너리를 활용하였습니다.

1. 만약 parent에 해당하는 숫자가 없다면 parent 를 생성하고 v+1 ( 자기자신보다 + 1 큰 노드를 가르키게 만든다)
2. 만약 parent에 해당하는 숫자가 있다면 parent의 노드를 재귀적으로 따라가서 parent에 없는 노드까지 따라간뒤 parent를 생성하고 그 해당하는 노드에 v+1를 가르키게 해준다.

💻 코드

import sys
sys.setrecursionlimit(int(1e9))

def solution(k, room_number):
    n = len(room_number)
    answer = []
    parent = {}
    
    def find(v):
        if v not in parent:
            parent[v] = v + 1
            return v
        parent[v] = find(parent[v])
        return parent[v]

    for number in room_number:
        available_room = find(number)
        answer.append(available_room)

    return answer