2019 카카오 개발자 겨울 인턴십 풀이

Level 1 - 크레인 인형뽑기 게임 풀이
Level 2 - 튜플 풀이
Level 3 - 불량 사용자 풀이
Level 4 - 호텔 방 배정 풀이
Level 3 - 징검다리 건너기 풀이

프로그래머스 - 호텔 방 배정 링크
(2022.11.01 기준 Level 4)

문제

방이 총 k개 있고 각 방은 1번부터 k번까지의 번호로 구분되는 호텔이 있다. 고객들이 신청한 순서대로 원하는 방 번호 리스트가 있을 때, 방이 비어있다면 즉시 배정해주고, 아니면 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정해주게 된다.
이 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 반환

풀이

Union-Find 함수를 이용해 부모 노드를 찾는 느낌으로 하면 좋겠지만.. k가 최대 1,000,000,000,000이다. 그러므로 해시를 이용하여 부모 노드를 찾는 느낌으로 방 배정을 구현하면 된다.

알고리즘

Union-Find에서 Find는 부모 노드를 찾아 내는 것이다. 자기와 같은 숫자이거나 -1로 저장되어 있는 경우가 대부분이고.
하지만 이 문제는 k의 최대가 1조여서 너무 크다. 그러므로 필요한 방 번호만 즉각 생성하는 느낌의 해시와 맵을 이용해야 한다.
파이썬에선 defaultdict가 있다.
일단 defaultdict(int)로 맵을 생성하자.
그러면 디폴트값은 0으로 저장되게 되고, 모든 방 번호는 1부터 k까지라서 신청하려는 방 번호에 대한 값이 0이 나오면 아직 배정되지 않은 방 번호라 할 수 있다.
그러면 이 방 번호로 배정해주면 된다. 배정한 다음에는? 다음 사람이 이 번호를 신청하게 되면 최소 +1 번호부터 검토하게 된다. 그래서 번호 + 1을 값으로 저장해두면 된다.

배정하는 행동을 함수로 만들어서 재귀적으로 구현해줘야 한다.
top-down dp처럼 0이 나올 때까지 반복하고 배정하게된 번호 + 1을 거쳐온 번호에 전부 저장해주면 되는 것이다.

이게 끝이다. 되게 간단해 보이지만, 생각해내기 꽤 어려웠다.
이해가 바로 가지 않는다면 코드를 보고 이해를 해보자

코드

import sys
sys.setrecursionlimit(100000) # 재귀 제한를 늘리자. 늘리지 않으면 런타임 에러
from collections import defaultdict

def solution(k, room_number):

    def find(n): # 배정할 방 번호를 찾는 함수
        m = assign[n] # n번이 배정됐는지 확인

        if not m: # 배정이 되지 않았다면
            answer.append(n) # n번을 배정해주고
            assign[n] = n + 1 # 다음엔 n번을 신청하게 되면 n + 1번을 검토하게 한다.
            return n + 1

        # 배정이 된 상태라면
        # 검토할 번호로 하여금 다시 신청한다.
        result = find(m) # 살펴보게 할 최종 방 번호를
        assign[n] = result # 거쳐온 신청한 방 번호 모두에 저장
        return result

    # 방 번호가 배정이 됐는지 확인해야 한다. 각 번호를 맵으로 사용
    # 만약 assign[i]이 0이면 i는 아직 배정이 되지 않은 방 번호
    # 1 이상이면 이미 배정이 되었고 assign[i] 값은 다음에 검토할 번호가 저장이 된다.
    assign = defaultdict(int)
    answer = []
    for number in room_number:
        find(number)

    return answer

여담

union-find 함수에서 아이디어를 얻어 풀어낸 문제.
진짜 union-find 함수를 써보려고 했는데 좀 어려워서 그냥 생각나는 대로 풀었다.