호텔 방 배정

• Disjoint Set을 사용해서 푸는 문제이다.
• 어떤 방을 요청할 때 실제로 같은 방으로 배정되는 방들을 하나의 집합으로 유지하면 된다
• 구체적으로, n번부터 m-1번까지의 방이 모두 차 있는 상태라면, 다음에 n번부터 m번 사이의 방으로 요청이 들어오면 m번에 배정을 해줘야 한다. 이것은 n부터 m까지는 같은 집합이고, 그 집합의 다음 배정 예정방은 m으로 매핑이 되어있는 상태로 표현된다
• 여기에서 n번방에 요청이 들어와서 m번방에 배정을 하게 된다면 다음 배정 예정방을 업데이트 해줘야 한다. n번방이 속한 집합과 m+1번 방이 속해있는 집합을 합치고, 합쳐진 집합의 배정 예정방은 원래 m+1번방에 대한 배정 예정방이 된다.
• 여기에서는 teflib의 disjoint set을 이용해서 구현했지만, 보통은 기존 구현된 disjoint set을 재활용하는 것보다, 그냥 disjoint set의 아이디어만 사용해서 문제에 맞춰 새로 구현하는 것이 더 간단할 수도 있다. 구현된 disjoint set을 재활용하려면 집합을 배정 예정방으로 매핑하는 딕셔너리가 하나 더 필요하기 때문이다. 또한, k가 너무 큰 관계로, k개의 방을 모두 집합으로 처음에 만들어 두는 대신에, 요청이 들어온 방만 처음 들어올때 집합을 생성하는 처리도 필요하다. 안그러면 런타임 에러가 난다.
• room_number 배열의 크기만큼 find와 union연산이 필요하다. 시간복잡도는 O(α(n)*n) (n은 room_number 배열의 크기, α(n)은 애커만 함수)

"""Solution code for "Programmers 64063. 호텔 방 배정".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/64063
- Solution link: http://www.teferi.net/ps/problems/programmers/64063
"""

from teflib import disjointset


def solution(k, room_number):

    def best_available_room(requested_room):
        s = djset.find(requested_room)
        try:
            return room_by_set[s]
        except KeyError:
            return s

    answer = []
    djset = disjointset.DisjointSet()
    room_by_set = {}
    for requested_room in room_number:
        assigned_room = best_available_room(requested_room)
        answer.append(assigned_room)
        next_available_room = best_available_room(assigned_room + 1)
        merged_set = djset.union(requested_room, assigned_room + 1)
        room_by_set[merged_set] = next_available_room
    return answer

• Dependency: teflib.disjointset.DisjointSet