[호텔 방 배정/LV4/Python3]

프로그래머스 호텔 방 배정 LV4

 

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
한 번에 한 명씩 신청한 순서대로 방을 배정합니다. 고객은 투숙하기 원하는 방 번호를 제출합니다. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

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

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

 

 

Union Find 분리 집합 알고리즘을 사용하여 풀이를 진행했다.

해당 알고리즘 구현을 위해 Dictionary를 사용했다.

 

k의 범위가 10^12로 많이 큰 문제이다.

통과된 코드와 구조는 같더라도 부모를 만드는 방식으로는 시간초과에 걸려 통과하지 못 했다.  p = [i for i in range(k+1)]

 

 

코드의 실행 방식은 다음과 같은 순서를 따라간다.

1. Find()함수로 딕셔너리에 없는 방이 있을 때까지 재귀적으로 탐색한다.

2. 찾은 방을 제공하고, 해당 방은 딕셔너리의 키로 값으로는 해당 방+1를 가지도록 딕셔너리에 저장한다.

3. 제공된 방을 정답을 담을 변수에 추가한다.

 

 

import sys
sys.setrecursionlimit(10**6)

def solution(k, room_number):
    parent = {}
    answer = [0] * len(room_number)
    
    def find(v):
        if v not in parent:
            parent[v] = v+1
            return v
        parent[v] = find(parent[v])
        return parent[v]
    
    for i in range(len(room_number)):
        r_f = find(room_number[i])
        answer[i] = r_f
        parent[r_f] = r_f+1
    
    
    return answer

 

---

 

백준 10775번 공항 문제와 유사한 문제이다.

입력 제한도 여유로운 편이기에 해당 문제를 먼저 풀고 접근하면 조금 더 쉽게 풀 수 있다.