[프로그래머스] 호텔 방 배정 - 자바 Java

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

프로그래머스

 

문제

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

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

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

---

입출력

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

---

풀이

원하는 방이 이미 배정되었을 때, 그 방보다 큰 첫 번째 가능한 방을 찾아야 한다. 따라서 HashMap을 사용하여 각 방 번호에 대해 다음으로 사용 가능한 방 번호를 저장한다. `roomMap.put(예약된 방, 다음으로 예약 가능한 방)`

 

 

전체코드

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        HashMap<Long, Long> roomMap = new HashMap<>();  // 다음 사용 가능한 방 번호를 저장
        int n = room_number.length;
        long[] answer = new long[n];
        
        for (int i = 0; i < n; i++) {
            answer[i] = findEmptyRoom(room_number[i], roomMap);
        }
        
        return answer;
    }
    
    public long findEmptyRoom(long want, HashMap<Long, Long> roomMap) {
        // 원하는 방이 비어있으면 바로 배정
        if (!roomMap.containsKey(want)) {
            roomMap.put(want, want + 1);  // 다음 사용 가능한 방을 want + 1로 설정
            return want;
        }
        
        // 이미 배정된 방이면 재귀적으로 다음 방 찾기
        long nextRoom = findEmptyRoom(roomMap.get(want), roomMap);
        roomMap.put(want, nextRoom + 1);  // 현재 방의 다음 가능한 방 업데이트
        return nextRoom;
    }
}

 

1단계) room_number[0] = 1 요청 결과 roomMap에는 `{1 → 2}`이 저장되어 있다.

2단계) room_number[1] = 3 요청 결과: `{1 → 2, 3 → 4}`

3단계) room_number[2] = 4 요청 결과: `{1 → 2, 3 → 4, 4 → 5}`

4단계) room_number[3] = 1 요청 결과: `{1 → 3, 2 → 3, 3 → 4, 4 → 5}`

• 1은 이미 사용 중이다. 1 → 2를 통해 확인할 수 있다.
• 2번 방을 배정한다. (2 → 3 추가)
• 1의 다음 방을 3으로 업데이트한다. (1 →  3)

5단계) room_number[4] = 3 요청 결과: `{1 → 3, 2 → 3, 3 → 6, 4 → 6, 5 → 6}`

• 3은 이미 사용 중이다. 3 → 4를 통해 확인
• 4도 이미 사용 중이다. 4 → 5를 통해 확인
• 그 다음 큰 방인 5번 방을 배정한다. (5 → 6 추가)
• 4 → 6으로 업데이트
• 3 → 6으로 업데이트

...