[Programmers] 호텔 방 배정

ㅇ

문제

 

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

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

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

배정된 방 번호

[1, 3, 4, 2, 5, 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] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

---

풀이

풀이1 (반복문, 효율성 0점)

 

첫번째 풀이는 풀이 방법 그대로 하라는 대로 구현해서 풀어본 방법이다.

정확성은 맞으나 효율성 0점 짜리 ㅠㅜ

def solution(k, room_number):
    answer = []
    visit = [0] * (k+1)
    
    for i in room_number:
        if visit[i] != 0:
            for j in range(i+1, k+1):
                if visit[j] == 0:
                    answer.append(j)
                    visit[j] = 1
                    break
        else:
            answer.append(i)
            visit[i] = 1
    
    return answer

 

풀이2 (재귀 사용, 효율성 1개 맞음)

두번째 풀이를 할때부터 약간 감을 잡아갔다.

재귀를 이용해서 방이 비어있지 않다면

이 방을 원한 고객이 몇명이었는지를 방 숫자에 더해서 배열에 저장해두면 바로 찾을 수 있지 않나?

결과는 효율성 3점 ㅠㅜ

def solution(k, room_number):
    answer = []
    visit = [0] * (k+1)
    
    def sol(i):
        if visit[i]:
            sol(i+visit[i])
        else:
            answer.append(i)
        visit[i] += 1       

    for i in room_number:
        sol(i)

    return answer

 

 

 

풀이3 (재귀 사용, 효율성 다맞음)

뭔가 잡힐듯 안잡혀서 힌트를 보고 다시 풀어봤다.

일단 런타임 에러와 시간초과가 다른건가에 대한 의문이 풀렸다.

시간초과는 말 그대로 정해둔 시간에 완료되지 못해서 실패한 것이고,

런타임에러는 아마도 최대 깊이를 초과해서 재귀가 호출되어서 그런 것 같다.

 

문제에 "k는 1 이상 1012 이하인 자연수입니다." 라고 나와있기 때문에 최대 깊이를 임의로 늘려준다.

 

다음 리스트로 채워졌는지를 확인하던 것을 dictionary로 바꿨다.

리스트는 인덱싱을 사용하기 위해서는 먼저 k+1번까지 반복해서 미리 만들어둬야 하는데

딕셔너리는 그럴 필요 없이 i번 방에 들어가겠다는 요청이 처음 있을 때, i번 방을 생성할 수 있다.

import sys
sys.setrecursionlimit(10000) 

def solution(k, room_number):
    answer = []
    visit = dict()
    
    def sol(i):
        if i in visit.keys():
            t = sol(visit[i])
            visit[i] = t+1
            return t
        else:
            visit[i] = i+1
            answer.append(i)
            return i

    for i in room_number:
        sol(i)

    return answer