프로그래머스: 호텔 방 배정 (Level 4)

import java.util.*;
class Solution {
    public long[] solution(long k, long[] room_number) {
        Map<Long, Long> map = new HashMap<Long, Long>();
        
        for(int i=0; i<room_number.length; i++){
            
            long start = room_number[i];
            
            while(true){
                long jump = map.getOrDefault(start, start-1);
                if(jump+1 == start){
                  break;  
                } 
                start = jump+1;
            }
            
            map.put(room_number[i] , start);
            room_number[i]=start;
            
        }
        
        
        return room_number;
    }
}

while(true){
    long jump = map.getOrDefault(start, start-1);
    if(jump+1 == start){
      break;  
    } 
    start = jump+1;
}

map.put(room_number[i], start);  // 요청 번호 → 배정 번호

map: {방 번호 → 다음 빈 방 번호}

예: 1, 2, 3이 차있으면
map = {1→4, 2→4, 3→4}

4 요청 시:
- map에 4 없음 → 4 배정
- map.put(4, 5)

5 요청 시:
- map에 5 없음 → 5 배정
- map.put(5, 6)

1 다시 요청 시:
- map.get(1) = 4
- map.get(4) = 5
- map.get(5) = 6
- 6 배정!
- Path Compression: map.put(1, 6) ← 최적화!

import java.util.*;

class Solution {
    Map<Long, Long> parent = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] result = new long[room_number.length];
        
        for (int i = 0; i < room_number.length; i++) {
            result[i] = findEmpty(room_number[i]);
        }
        
        return result;
    }
    
    // 빈 방 찾기 + Path Compression
    private long findEmpty(long room) {
        // 방이 비어있으면
        if (!parent.containsKey(room)) {
            parent.put(room, room + 1);  // 다음 빈 방은 room+1
            return room;
        }
        
        // 방이 차있으면 다음 빈 방 찾기
        long empty = findEmpty(parent.get(room));
        parent.put(room, empty);  // Path Compression!
        return empty;
    }
}

private long findEmpty(long room) {
    if (!parent.containsKey(room)) {
        parent.put(room, room + 1);
        return room;
    }
    
    long empty = findEmpty(parent.get(room));
    parent.put(room, empty);  // ← 이 줄이 핵심!
    return empty;
}

import java.util.*;

class Solution {
    Map<Long, Long> next = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] result = new long[room_number.length];
        
        for (int i = 0; i < room_number.length; i++) {
            result[i] = findEmptyRoom(room_number[i]);
        }
        
        return result;
    }
    
    /**
     * 빈 방 찾기 (Union-Find with Path Compression)
     * @param room 원하는 방 번호
     * @return 배정된 방 번호
     */
    private long findEmptyRoom(long room) {
        // 방이 비어있으면 배정
        if (!next.containsKey(room)) {
            next.put(room, room + 1);
            return room;
        }
        
        // 방이 차있으면 다음 빈 방 재귀 탐색
        long emptyRoom = findEmptyRoom(next.get(room));
        
        // Path Compression: 경로 압축
        next.put(room, emptyRoom);
        
        return emptyRoom;
    }
}

/**
 * 시간복잡도: O(n × α(n)) ≈ O(n)
 * 공간복잡도: O(n)
 * 
 * α(n): 역 아커만 함수 (실질적으로 상수)
 */

// 원본
map.put(room_number[i], start);  // 요청 → 배정
long jump = map.getOrDefault(start, start-1);  // 배정으로 조회?

// 올바른 방법
next.put(room, room + 1);  // 현재 방 → 다음 빈 방
long nextRoom = next.get(room);  // 현재 방으로 다음 방 조회

// 원본: while로 순차 탐색
while(true){
    long jump = map.getOrDefault(start, start-1);
    if(jump+1 == start) break;
    start = jump+1;
}

// 개선: 재귀 + Path Compression
long empty = findEmpty(next.get(room));
next.put(room, empty);  // 압축!

class UnionFind {
    Map<Integer, Integer> parent = new HashMap<>();
    
    // Find with Path Compression
    int find(int x) {
        if (!parent.containsKey(x)) {
            parent.put(x, x);
            return x;
        }
        if (parent.get(x) != x) {
            parent.put(x, find(parent.get(x)));  // 압축
        }
        return parent.get(x);
    }
    
    // Union
    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent.put(rootX, rootY);
        }
    }
}