[Programmers] 호텔 방 배정 (Java)

https://programmers.co.kr/learn/courses/30/lessons/64063

코딩테스트 연습 - 호텔 방 배정

 

호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분됩니다.

 

배정 규칙

1. 한 번에 한 명씩 신청한 순서대로 배정됩니다.

2. 고객은 투숙하기 원하는 방 번호를 제출합니다.

3. 고객이 원하는 방이 비어있따면 즉시 배정합니다.

4. 고객이 원하는 방이 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

 

문제 풀이

해당 문제는 Union-Find를 활용하여 풀어야 합니다.

Union-Find는 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다.

트리 구조가 완전 비대칭일 때, Union-Find를 통해 부모노드까지의 경로를 압축시킬 수 있습니다.

이 방법을 이용해 요청한 방이 비어있지 않은 경우에 안내할 방을 빠르게 찾을 수 있도록 연결해주면 됩니다.

 

고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 3] 일 때 처음 고객은 본인이 원하는 방인 1번 방을 얻을 수 있습니다.

그러면 다음 고객은 1번 방이 아닌 비어있는 가장 작은 번호인 2번 방에 안내를 받아야 합니다.

그 다음 고객이 3번 방을 요청하면 위와 같은 방식으로 다음에 배정해줄 방을 4번으로 지정해둡니다.

만약, 그 전에 4번 방을 요청한 고객이 있어 4번 방이 배정되면, 이후 3번 방을 요청한 고객은 아래와 같은 방식을 통해 5번 방을 배정받게 됩니다.

고객들이 원하는 방 번호가 순서대로 [1, 3, 2, 2] 라면 처음 세 고객은 순서대로 1번, 3번, 2번 방을 배정받게 됩니다.

이후 2번 방을 배정받은 고객은 아래와 같은 방식으로 4번 방을 배정받게 됩니다.

 

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    static HashMap<Long, Long> roomInfo = new HashMap<>();

    public long findEmptyRoom(long wantRoom) {
        if (!roomInfo.containsKey(wantRoom)) { // 요청한 방이 비어있음
            roomInfo.put(wantRoom, wantRoom + 1); // 다음 방 연결
            return wantRoom;
        }

        long next_room = roomInfo.get(wantRoom);
        long empty_room = findEmptyRoom(next_room);
        roomInfo.put(wantRoom, empty_room);
        return empty_room;
    }
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];

        for (int i = 0; i < room_number.length; i++) {
            answer[i] = findEmptyRoom(room_number[i]);
        }

        return answer;
    }
}