[ 카카오 / Python ] 2019 카카오 개발자 겨울 인턴십 - 호텔 방 배정

문제 설명

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

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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]

풀이

효율성 검사가 있는 문제로, 단순한 완전 탐색으로 절대 풀 수 없다.
그리고, K는 10^12 까지 존재할 수 있으므로 배열로 탐색을 한다면 메모리 초과가 발생할 수 있다.

그래서 defaultdict 클래스를 이용해서 문제를 풀이했다.

만약 원하는 방이 비어있는 상태라면, 즉 defaultdict 내에 키로 존재하지 않으면 바로 그 방을 배정해준다.

배정된 방은 더 이상 배정해 줄 수 없으니, 그 다음 방을 배정해주기로 생각하고 defaultdict에 room_number + 1을 넣어준다.

만약 원하는 방이 배정된 상태라면, 배정된 방이 없을 때까지 방을 찾으면서 돌아야 한다.

만약 1번 방이 배정되어 있어 defaultdict에 2로 방 배정이 되어있다면, 2번 방이 비어있을 때 defaultdict 에 2번 키는 3번 방으로 설정 되고, 이 재귀에서 빠져나와 1번 방 역시 3번 방으로 설정된다.

Union-Find 와 비슷한 알고리즘으로 동작하는 것 같다.

위 풀이는 해당 해설을 참고 하였다.

코드

import sys
from collections import defaultdict

sys.setrecursionlimit(10**5)

def find(rooms, want):
    room = want
    if rooms[room]:
        room = find(rooms, rooms[room])
    rooms[want] = room + 1
    return room


def solution(k, room_number):
    answer = []

    rooms = defaultdict(int)

    for want in room_number:
        answer.append(find(rooms, want))

    return answer