"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
- 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다.
- 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
- 고객은 투숙하기 원하는 방 번호를 제출합니다.
- 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
- 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
1차 접근 방법
- 처음에 10^12를 보지 못하고 중첩 반복문을 사용하려고 하였다.
- 아래와 같이 배정 여부를 저장하려고 했다.
booked = [0 for in range(k+1)]1차 접근 실패!
-> 접근성 테스트는 모두 통과 했지만, 10^12이다 보니 효율성 테스트에서 모두 실패했다.
2차 접근 방법
- 시간복잡도를 줄이는 것이 관건이라고 생각했다.
- O(logn)의 시간복잡도를 가지는 알고리즘을 찾기 시작했다.
- Union Find 알고리즘을 발견했고, 이를 사용하기로 결정했다.
제출 코드 (통과)
import sys
sys.setrecursionlimit(100000000)
def check_room(num, rooms):
if num not in rooms.keys():
rooms[num] = num + 1
return num
empty = check_room(rooms[num], rooms)
rooms[num] = empty + 1
return empty
def solution(k, room_number):
answer = []
room = {}
for i in room_number:
checkIn = check_room(i, room)
return list(room.keys())참고
호텔방배정
Hi~