호텔 방 배정

문제를 이해하는 거는 쉬웠지만 풀이 자체가 굉장히 어려웠던 문제다.

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호	배정된 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• k는 1 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

---

[입출력 예]

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

입출력 예에 대한 설명

입출력 예 #1

문제의 예시와 같습니다.

첫 번째 ~ 세 번째 고객까지는 원하는 방이 비어 있으므로 즉시 배정받을 수 있습니다. 네 번째 고객의 경우 1번 방을 배정받기를 원했는데, 1번 방은 빈 방이 아니므로, 1번 보다 번호가 크고 비어 있는 방 중에서 가장 번호가 작은 방을 배정해야 합니다. 1번 보다 번호가 크면서 비어있는 방은 [2번, 5번, 6번…] 방이며, 이중 가장 번호가 작은 방은 2번 방입니다. 따라서 네 번째 고객은 2번 방을 배정받습니다. 마찬가지로 5, 6번째 고객은 각각 5번, 6번 방을 배정받게 됩니다.

문제 풀이

효율을 생각하지 않고 푸는 방법은 간단하다. 배정되지 않은 방의 경우 즉각 배정하고, 배정된 경우에는 다음 빈방까지 찾아서 배정하면 된다. 이러면 매번 방이 중복되는 경우 루프를 돌려야하기 때문에 비효율적이다.

못 풀어서 다름 사람 풀이를 참고하니 UnionFind라는 알고리즘을 사용했다. 이는 합집합 찾기라는 자료 구조로 두가지 연산을 제공한다.

Find: 어떤 요소가 주어졌을 때, 해당 원소가 속한 집합의 대표을 반환한다.

Union: 두 개의 집합을 하나의 집합으로 합친다.

예를 들어, 4~10까지 모두 배정된 방들을 하나의 집합이라고 본다. 그리고 새로운 방 배정이 해당 집합에 속할 경우, 가장 오른방보다 큰 방인 11을 배정할 수 있다. 그리고 집합은 다시 4~11이 된다. 기본적인 find와 union은 다음과 같이 구현할 수 있다.

def find(x):
    if root[x] ==x:
        return x
    
    return find(root[x])

def union(x,y):
    x = find(x)
    y = find(y)
    root[y] = x

root는 배열로 각 원소의 부모 원소 위치를 가르킨다. 위 예에 적용하면 4~10 원소들은 해당 root 배열값에 10을 가지고 있다. 따라서 find는 자기 자신을 부모로 가지는 원소가 나올때까지 반복하여 부모 원소를 찾는다.

union은 서로의 루트를 찾은 뒤에 이어주는 역할을 한다. 하지만 위 문제에 적용할려면 union부분은 바뀌어야한다. 배정된 방보다 더 큰 방을 배정해야되므로 더 큰 값을 부모로 놓도록 바꾼다.

이를 이용해서 풀어보면

def solution(k, room_number):
    answer = []
    
	# 각 원소의 부모 노드를 가르키는 배열 root 생성
    global root
    root = list(range(k))
    
    # 방 배정
    for each_room in room_number:
        # 해당 룸의 부모 노드 찾기(비어있으면 본인 반환)
        parent = find(each_room-1)
        # 배정 받을 방에 다음 방 설정(union)
        root[parent] +=1
        # 방 배정
        answer.append(parent-1)
        
   	return answer

하지만 root의 크기 때문에 효율성에서 런타임 에러가 난다. 다른 사람의 풀이를 참조하여 이를 재귀적으로 풀도록 해본다.

def find(x, root):
    # 방이 비어있을 경우
    if x not in root:
        root[x] = x+1
        return x
    
    # 마지막 방 찾음
    parent = find(root[x], root)
    # 부모노드를 마지막 방 다음 방으로 지정
    root[x] = parent+1
    return parent

def solution(k, room_number):
    answer = []
    
	# 배열 대신 해시맵을 사용한다.
    root = dict()
    
    # 방 배정
    for each_room in room_number:
        # 해당 룸의 부모 노드 찾기(비어있으면 본인 반환)
        parent = find(each_room-1, root)
        answer.append(parent-1)
        
   	return answer