호텔 방 배정 (프로그래머스) JAVA

https://school.programmers.co.kr/learn/courses/30/lessons/64063?language=java 

프로그래머스

문제 설명

호텔에서 방 배정을 해줄 때, 4가지 조건에 맞게 방 배정을 해줍니다.

예를 들어 1,3,4는 배정된 방이 없으므로 자신이 원하는 방에 배정이 됩니다. 다음 1은 1이 이미 배정되었으므로 그보다 큰 2에 3도 배정 안 된 방중 3보다 큰 5, 다음은 6이 배정 받는 형식입니다.

 

문제에 대한 아이디어

k수가 10^12이므로 배열로 만들면 안됩니다. 그러므로 Map이나 Set을 써서 방문했는지를 검사해야 할 것 같습니다.

문제는 현재 배정되지 않은 방 중 자신이 가고 싶은 방 보다 크면서 번호가 제일 작은 방을 찾아야 한다는 것 입니다.

 

유니온 파인드 사용하기

유니온 파인드를 사용해 배정된 방을 하나의 집합으로 만듭니다.

merge는 자신이 배정 받은 방 중 +1 또는 -1 과 머지를 합니다. 이렇게 하면 자신이 배정 받고 싶은 방 보다 큰 수 중 제일 작은 수를 쉽게 찾을 수 있습니다.

 

유니온 파인드 코드

    private static class Node {
        private int depth = 1; 
        private Node parent = null;
        private long max; // 최댓값
        
        public Node(long value){ // 생성자
            max = value;
        }
        
        public boolean isConnected(Node o){ // root가 같은지를 비교
            return root() == o.root();
        }
        
        public long max() { // 최댓값 return
            return root().max;
        }
        
        public void merge(Node o){ // 연결하기
            if(isConnected(o)) return;
            
            Node root1 = root();
            Node root2 = o.root();
            
            if(root1.depth > root2.depth){
                root2.parent = root1;
            } else if(root1.depth < root2.depth){
                root1.parent = root2;
            } else {
                root2.parent = root1;
                root1.depth += 1;
            }
            
            root1.max = root2.max = Math.max(root1.max, root2.max);
        }
            
            private Node root() { // root 리턴
                if (parent == null) return this;
                return parent.root();
            }
    }

 

전체 코드

import java.util.*;

class Solution {
    private static class Node {
        private int depth = 1;
        private Node parent = null;
        private long max;
        
        public Node(long value){
            max = value;
        }
        
        public boolean isConnected(Node o){
            return root() == o.root();
        }
        
        public long max() {
            return root().max;
        }
        
        public void merge(Node o){
            if(isConnected(o)) return;
            
            Node root1 = root();
            Node root2 = o.root();
            
            if(root1.depth > root2.depth){
                root2.parent = root1;
            } else if(root1.depth < root2.depth){
                root1.parent = root2;
            } else {
                root2.parent = root1;
                root1.depth += 1;
            }
            
            root1.max = root2.max = Math.max(root1.max, root2.max);
        }
            
            private Node root() {
                if (parent == null) return this;
                return parent.root();
            }
    }
    public long[] solution(long k, long[] room_number) {
        List<Long> assigned = new ArrayList<>();
        
        Map<Long, Node> nodes =new HashMap<>(); // 배정 했는지 검사
        for(long number : room_number){
            if(nodes.containsKey(number)){ // 배정 했으면 최댓값 + 1
                number = nodes.get(number).max()+1;
            }
            
            Node node = new Node(number);
            nodes.put(number, node);
            
            // merge 하기
            if(nodes.containsKey(number-1)){ 
                node.merge(nodes.get(number-1));
            }
            if(nodes.containsKey(number+1)){
                node.merge(nodes.get(number+1));
            }
            
            assigned.add(number);
        }
        
        return assigned.stream().mapToLong(Long::longValue).toArray();
    }
}