프로그래머스: 호텔 방 배정[레벨 4] / Java

 

 

 

프로그래머스: 호텔 방 배정

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

 

 

문제 설명

한 고객이 원하는 방 번호가 이미 배정되어 있다면,

해당 방 번호보다 큰 방 중 비어 있는 가장 가까운(작은) 번호의 방을 찾아 배정해야 한다.
각 고객은 한 번씩만 방문하고, 방의 개수는 매우 크기 때문에(최대 10¹²) 효율적인 탐색이 필요하다.

---

1차 시도 (오답)

보자마자 유니온-파인드 방식을 사용하려 했지만, k값이 10의 12제곱으로 매우 커 배열로 관리하기는 힘들어 보였다.

그래서 HashMap을 사용해 필요한 방 번호만 활성화해 관리하고자 했다.

 

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        int size = room_number.length;
        long[] answer = new long[size];
        
        Map<Long, Long> rooms = new HashMap<>();
        Map<Long, ArrayList<Long>> waitings = new HashMap<>();
        
        int idx = 0;
        for (long num : room_number) {
            
            if (rooms.get(num) == null) { // 미배정
                answer[idx++] = num;
                long nextRoom = num + 1;
                
                if (rooms.get(nextRoom) == null)
                    rooms.put(num, nextRoom);
                else
                    rooms.put(num, rooms.get(nextRoom));
                
                if (waitings.get(nextRoom) == null)
                    waitings.put(nextRoom, new ArrayList<>());
                waitings.get(nextRoom).add(num);

                if (waitings.get(num) != null) {
                    for (long w : waitings.get(num)) {
                        rooms.put(w, nextRoom);
                        waitings.get(nextRoom).add(w);
                    }
                    waitings.get(num).clear();
                }
                continue;
            }

            answer[idx++] = rooms.get(num);
            long nextRoom = rooms.get(num) + 1;
            
            if (rooms.get(nextRoom) == null)
                rooms.put(num, nextRoom);
            else
                rooms.put(num, rooms.get(nextRoom));
        }
        return answer;
    }
}

 

 

• rooms: key=방번호, value=가장 가까운 다음 방번호
• waitings: key = 방번호, value= 해당 방을 가리키고 있는 다른 방들의 리스트

방 배정 관계를 연결 리스트처럼 갱신하는 접근이었다.
배정된 방 번호를 key로, 다음 후보 방 번호를 value로 두면 된다 생각했다.

 

그러나 실제로 돌려보니 중복 배정이 발생하거나, 방 번호가 꼬이는 현상이 있었다.

1. rooms.put(num, nextRoom)만 갱신 → 요청 번호 기준으로만 갱신됨
   • 실제로 배정된 방 번호가 아니라 “희망 번호”를 기준으로 갱신해서 체인 구조가 끊기거나 잘못 연결됨.
2. 과도한 복잡성
   
   • waitings 리스트를 매번 돌며 일괄 갱신하다보니 너무 많은 갱신이 필요해 최악의 경우 O(N²)로 커졌고,
     코드를 작성하는 것도 너무 복잡했다.

---

2차 시도 (성공)

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        int size = room_number.length;
        long[] answer = new long[size];
        int idx = 0;
        Map<Long, Long> p = new HashMap<Long, Long>();
        
        for (long r : room_number) {
            long assigned = find(r,p);
            answer[idx++] = assigned;
            p.put(assigned, find(assigned+1,p));
        }
        
        return answer;
    }
    public long find(long x, Map<Long, Long> p) {
        if (p.get(x)== null) {
            return x;
        }
        long parent = find(p.get(x), p);
        p.put(x, parent);
        return parent;
    }
}

 

union-find 방식이 맞았다.

 

parent배열을 관리할 때, 배열로 관리하지 않고 Map으로 관리하면 되었다.

 

나는 find메서드를 호출할 때 최대 20만개의 방이 있을 수 있으니 스택오버플로우가 발생할거라 생각했다.

 

하지만 실제로 구현해보니 발생하지 않았다. 테스트케이스가 그렇게까지 극한으로 가진 않은 모양이다.

 

만약 테스트케이스가 [1, 1, 1, 1, .....] 이렇게 20만 개짜리 배열이 들어온다면,

 

1 > 2> 3> 4> .... > 200000

 

까지 경로 압출 없이 스택을 타고 들어가 스택오버플로우가 발생할 수 있을 것이다.

 

이를 해결하려면, 스택 대신 while문으로 구현해야할 것 같다.

 

회고

처음엔 단순히 HashMap으로 방 배정 상태를 추적하면 될 줄 알았다.
하지만 이 문제의 본질은 다음 비어있는 노드를 효율적으로 찾는 연결 관계를 만드는 것이다.

불필요한 리스트 관리보다 경로 압축 기반 union-find탐색이 훨씬 명확하고 빠르다.

 

결론은 너무 복잡하게 생각하지 말자..