Programmers - 호텔 방 배정[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/64063

코딩테스트 연습 - 호텔 방 배정

문제 설명

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

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

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

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

제한 사항

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

 

입출력 예

문제 풀이

효율성 테스트를 통과하지 못해 해설을 보고 푼 문제이다. 이전에 업로드한 서로소 집합 알고리즘의 find함수와 유사하게 문제를 해결할 수 있다. 재귀 함수에 대해서 간단하게 설명하자면

• 1. 방이 있는 경우(room_dict[value] = 0) room을 배정하고 해당 room의 값보다 1 큰 수를 부모 노드로 생성한다.
• 2. 방이 없는 경우(room_dict[value] != 0) 해당 room 보다 값이 큰방부터 탐색하여 비어있는 room 중 가장 값이 작은 room을 배정해야 하므로 해당 room의 부모 노드부터 탐색하여 비어있는 room을 찾는다. 이후 1번 과정을 수행한다.

주의해야 할 점은 방이 없는 경우 부모 노드를 거슬러 올라가며 방을 탐색할 때 경로 압축 기법을 사용하여 거슬러 올라간 자식 노드의 부모를 비어있는(room_dict[room] = 0) room번호로 갱신하여 시간복잡도를 개선하여야 한다.   

 

구현 코드

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def find_room(room_dict, room):
    if room_dict[room] == 0:
        room_dict[room] = room + 1
        return room
    elif room_dict[room] != 0:
        room_dict[room] = find_room(room_dict, room_dict[room])
        return room_dict[room]
    
def solution(k, room_number):
    room_dict = defaultdict(lambda : 0)
    result = []
    for room in room_number:
        result.append(find_room(room_dict, room))
    return result