(카카오)호텔 방 배정(문제54)

이 파트는 취이코전 풀이보다 재미니가 나음.

import java.util.*;
 
class Solution {
    // 배열 대신 Map을 사용하여 필요한 방 정보만 저장합니다.
    // Key: 이미 배정된 방, Value: 그 방 대신 가야 할 다음 방
    Map<Long, Long> parentMap = new HashMap<>();
 
    public long[] solution(long k, long[] room_numbers) {
        long[] answer = new long[room_numbers.length];
 
        for (int i = 0; i < room_numbers.length; i++) {
            long requestedRoom = room_numbers[i];
            long assignedRoom = find(requestedRoom);
            answer[i] = assignedRoom;
        }
 
        return answer;
    }
 
    /**
     * 지정된 방 번호(room)에 대해 배정 가능한 실제 방 번호를 찾습니다.
     * Union-Find 알고리즘의 'find' 연산과 경로 압축을 수행합니다.
     * @param room 원하는 방 번호
     * @return 배정 가능한 방 번호
     */
    private long find(long room) {
        // 1. 이 방이 Map에 없다면, 아직 비어있다는 의미입니다.
        if (!parentMap.containsKey(room)) {
            // 2. 이 방을 배정하고, 다음 요청자를 위해 (room + 1)을 가리키도록 설정합니다. (Union 연산)
            parentMap.put(room, room + 1);
            return room;
        }
 
        // 3. 이 방이 이미 차있다면, 이 방이 가리키는 다음 방으로 가서 빈 방을 찾습니다. (재귀 호출)
        long nextRoom = parentMap.get(room);
        long emptyRoom = find(nextRoom);
 
        // 4. 경로 압축: 현재 방이 최종적으로 찾은 빈 방을 직접 가리키도록 업데이트합니다.
        // 이렇게 하면 다음번에 이 방을 찾을 때 훨씬 빨라집니다.
        parentMap.put(room, emptyRoom);
        
        return emptyRoom;
    }
}
 

import java.util.*;
class Solution {
    public long[] solution(long k, long[] roomNumbers) {
        //k는 최대 1억, roomNumbers는 200,000개 최대
        //1~K 방번호 존재
        //이미 방이 배정되어있다면 그 방보다 번호가 크면서 빈곳중 번호가 젤 작은거
        
        DisjointSet disjointSet = new DisjointSet(k);
        List<Long> ansList = new ArrayList<>();
        for(long roomNumber : roomNumbers){
            long rootRoomNumber = disjointSet.find(roomNumber);
            
            if(rootRoomNumber != roomNumber){
                //지금 가져돈 루트를 방으로 배정하고 이 루트를 +1쪽으로 합친다.
                ansList.add(rootRoomNumber);
                disjointSet.union(rootRoomNumber, disjointSet.find(rootRoomNumber + 1));
                
            }else{
                ansList.add(rootRoomNumber);
                disjointSet.union(rootRoomNumber, disjointSet.find(rootRoomNumber + 1));
            }
        }
        long[] ans = new long[ansList.size()];
        for(int i=0 ; i<ans.length ; i++){
            ans[i] = ansList.get(i);
        }
        return ans;
    }
    
    class DisjointSet{
        List<Long> parents = new ArrayList<>();
        
        public DisjointSet(long n){
            for(long i=0 ; i<n ; i++){
                parents.add(i);
            }
        }
        
        public void union(long u, long v){
            long rootU = find(u);
            long rootV = find(v);
            
            if(rootU != rootV){
                parents.set(rootU, parents.get(rootV));
            }
        }
        
        public long find(long u){
            if(parents.get(u) == u){
                return u;
            }
            
            parents.set(u, find(parents.get(u)));
            return parents.get(u);
        }
    }
}