2019 카카오 개발자 겨울 인턴쉽 - 호텔 방 배정(경로 압축) - Java 풀이

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

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

- 방의 갯수가 최대 1e12 1조이고, 고객들이 요청하는 방 갯수는 20만이다. 고객들이 요구한 번호의 방 혹은 번호가 크면서 비어있는 방 중 가장 번호가 작은 방이라는 조건이 있기 때문에 해시맵으로 사용된 방과 사용할 수 있는 그 다음 방을 해쉬맵에 기록하는 방식으로 접근하였다. 

- 방을 길이 k의 1차원배열로 생각했을 때 방 정보를 업데이트 할 때마다 해당 방의 오른쪽으로 연결되어있는 방들에 대하여 다음 제공할 수 있는 방 정보에 대해 경로압축을 해놓으면 사용가능한 다음 방을 logM 혹은 a(M)안에 찾을 수 있다.(M은 시작지점으로부터 오른쪽으로 이미 배정되어있는 방들이 이어진 길이에 대해서 경로압축 했을 경우 아커만 함수에 따라 최대 5), 따라서 Nlog(M) = 손님 20만 * 방탐색 log(20만) 복잡도로 풀 수 있다. 

- 그동안 배열이나 그래프, 트리에서 disjoint Set을 구현하기 위해 유니온 파인드를 자주 사용하곤 했는데, 이미 사용된 방에 대하여 다음 사용가능한 다음 방을 표현하기 위해 해시맵으로 구현해야되는 문제이다.

import java.util.*;

class Solution {
    Map<Long, Long> map = new HashMap<>(); // {now:next}
    
    public long[] solution(long k, long[] room_number) {
        int N = room_number.length;
        long[] ans = new long[N];
        
        for(int i = 0; i < N; ++i) {
            ans[i] = find(room_number[i]);
        }
        
        return ans;
    }
    
    long find(long x) {
        if(map.get(x) == null) {
            map.put(x, x + 1);
            return x;
        }
        
        long y = find(map.get(x));
        map.put(x, y);
        return y;
    }
}