[프로그래머스, 64063] 호텔 방 배정 (java)

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

프로그래머스

---

메모리: 149 MB, 시간: 369.50 ms

사용 알고리즘: 구현

 

map에 방 번호를 key로, key번 방을 선택했을 경우 배정해야 하는 방 번호를 value로 저장한다.

key에 해당하는 값이 map에 없다면 아직 key번 방을 배정한 적이 없다고 간주하고 key번 방에 배정을 한 뒤,

다음 방 번호인 key + 1을 value로 저장한다.

만약 key가 map에 있다면, 이미 key번 방에 배정된 손님이 있는 것이므로 다음 배정할 방 번호인 value로 이동하여 비어있는 방을 찾을 때까지 이동한다.

 

유니온 파인드의 find 메소드 개념과 비슷하게 구현한 것 같다.

import java.util.*;

class Solution {
    
    static Map<Long, Long> map;
    
    public long[] solution(long k, long[] room_number) {
        
        long[] answer = new long[room_number.length];
        
        map = new HashMap<>();
        
        for(int i = 0; i < room_number.length; i++) {
            answer[i] = getEmptyRoom(room_number[i]);
        }
        return answer;
    }
    
    private static long getEmptyRoom(long n) {
        
        // 배정 받을 방 번호
        Long emptyRoom = map.get(n);
        
        // n번 방이 아직 배정받지 않았다면
        if(emptyRoom == null) {
            map.put(n, n + 1); // 다음 배정받을 방을 가리키고
            return n; // n번 방에 배정
        }
        
        // n번 방이 이미 배정받은 방이라면 다음 방을 찾아봄
        long room = getEmptyRoom(emptyRoom);
        map.put(n, room + 1);
        return room;
    }
}