Programmers. 호텔 방 배정

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 호텔 방 배정

문제 풀이

카카오 인턴에 출제된 문제다. 정확성 로직은 맞았는데 효율성에서 통과하지 못했다. 라이트업을 보니 유니온-파인드로 탐색 거리를 줄여야했다. 분명 공부했는데 떠올리지 못한 게 아쉽다.

각 방에 대해 요청을 하고 hash 자료구조에 요청하여 검색한 뒤 배정된 적이 없으면 answer 배열에 해당 방 번호를 추가하고 해당 방번호의 키에 다음 방을 입력해 다음에 다시 찾아왔을 경우 값이 가리키는 방으로 찾아가게끔 한다. 만약 이미 배정되었다면 갱신할 배열에 현재 방 번호를 추가하고 현재 방번호가 가리키는 방으로 다시 탐색한다.

• 갱신할 방 번호를 저장할 배열 선언
• 요청 받은 방번호부터 시작해 재귀 탐색
• 이미 배정된 방이면 갱신 배열에 현재 방 추가, 현재 방이 가리키는 다음 방으로 재탐색
• 배정된 방이 아니면 정답 배열에 현재 방 추가하고 이 다음 방문 시에는 다음 방으로 가도록 현재 방 번호 + 1로 값 저장한 뒤 이전 갱신 배열의 방들도 모두 바꿀 수 있도록 현재 방 번호 + 1 반환
• 반환받은 방 번호에 대해 갱신할 배열의 각 키 값도 수정(탐색거리 단축)

python 코드

import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict
def solution(k, room_number):
    def upward(x, buf):
        r = room_dict[x]
        if r == 0:
            room_dict[x] = x + 1
            answer.append(x)
            return x + 1
        buf.append(x)
        return upward(r, buf)
    def find(x):
        buf = []
        res = upward(x, buf)
        for b in buf:
            room_dict[b] = res
    answer = []
    room_dict = defaultdict(int)
    for room in room_number:
        find(room)
    return answer