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

[문제]

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

프로그래머스

[풀이]

해당 문제는 방을 배정하며, 해당 방 다음으로 올 수 있는 빈방을 연결해 계속 갱신해주며 풀이하는 문제입니다.

 

Map<Long, Long>을 사용하였는데, 해당 Map은 <방 번호 x, x 대신 배정될 수 있는 방 번호> 형식으로 저장됩니다.

입출력 예를 살펴보면, 풀이 과정은 다음과 같습니다.

 

room_number : [1,3,4,1,3,1] 

1. room_number를 탐색하며 방을 배정해 answer[]을 갱신합니다.
2. 만약, 해당 방 번호를 키로하는 값 x이 map에 존재하지 않는다면 아직 배정되지 않은방이므로 x를 배정하고, map에 <x, x+1> 값을 저장합니다. ( 이후 x가 들어왔을때 x+1을 배정해주기 위해서)
3. 만약, 해당 방 번호를 키로 하는 값 x가 map에 존재한다면, 이미 x는 배정됐으므로 while문을 통해 map에서 아직 배정되지 않은 방을 찾아서 해당 방번호 y를 배정합니다. 이때, map을 통해 거쳐온 방번호들은 모두 y+1로 갱신해줍니다.

위와 같은 과정을 거치고 나면 map의 변화는 다음과 같습니다.

{1=2}
{1=2, 3=4}
{1=2, 3=4, 4=5}
{1=3, 2=3, 3=4, 4=5}
{1=3, 2=3, 3=6, 4=6, 5=6}
{1=7, 2=3, 3=7, 4=6, 5=6, 6=7}

• 1번 방 배정 요구 -> map.get(1)은 null이므로 1번 배정후 map.get(1) = 2로 갱신
• 3번 방 배정 요구 -> map.get(3)은 null이므로 3번 배정후 map.get(3) = 4로 갱신
• 4번 방 배정 요구 -> map.get(4)은 null이므로 4번 배정후 map.get(4) = 5로 갱신
• 1번 방 배정 요구 -> 이미 배정된 방이므로, map을 따라가면 1->2->null 이므로 2번방 배정후
  map.get(1) = 3, map.get(2) = 3으로 각각 갱신
• 3번 방 배정 요구 -> 이미 배정된 방이므로, map을 따라가면 3->4->5-> null 이므로 5번방 배정후
  map.get(3) = 6, map.get(4) = 6, map.get(5) = 6으로 각각 갱신
• 1번 방 배정 요구 -> 이미 배정된 방이므로, map을 따라가면 1->3->6->null 이므로 6번방 배정후
  map.get(1) = 7, map.get(3) = 7, map.get(6) = 7으로 각각 갱신

따라서 answer = [1,3,4,2,5,6]이 됩니다.

[코드]

import java.util.*;
class Solution {
    public static Map<Long, Long> map = new HashMap<Long,Long>();
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        for(int i=0;i<room_number.length;i++) {
            long num = room_number[i];
            if(map.get(num) == null) {
                answer[i] = num;
                map.put(num, num + 1);
            } else {
                ArrayList<Long> list = new ArrayList<Long>();
                while(map.get(num) != null) {
                    list.add(num);
                    num = map.get(num);
                }
                answer[i] = num;
                map.put(num, num + 1);
                for(Long l:list) {
                    map.put(l,num + 1);
                }
            }
            System.out.println(map);
        }
        return answer;
    }
}