본문 바로가기

알고리즘/프로그래머스

[2019 카카오 개발자 겨울 인턴십] 호텔 방 배정(Union-Find, Java, 자세한 설명, 접근법)

## 접근


1. 처음에는 Set 자료구조를 이용해서 문제를 해결하려고 했다. 방번호들을 자료구조에 저장하여, 해당 방번호의 존재 유무를 확인하고 없으면 바로 정답에 넣어주고, 아니면 해당 방번호 + 1부터 가능한 방을 탐색해야 한다.

 

 

 

 

2. 해당 방번호 + 1에서 시작하여 빈 방을 찾을 때, 순차적으로 접근한다면 k가 10^12이기 때문에 시간복잡도 문제가 발생한다. 

 

 

 

 

3. Set 대신에 Map을 이용해서, 방번호를 Key로서 기억함과 동시에, Value로 다음 방번호를 찾게 하는 역할을 하게 만들고 싶다. 1, 3, 4, 1, 1을 생각해보면,

 

 

 

 

1 : Map에 미존재, M[1] = 2

 

3 : Map에 미존재, M[3] = 4

 

4 : Map에 미존재, M[4] = 5

 

1 : Map에 존재하므로, M[1]의 값 이용

  • M[1]의 값인 2을 사용하기 위해서, M[2]를 확인
  • M[2]는 미존재이므로, M[2] = 3

1 : Map에 존재하므로, M[1]의 값을 이용

  • 이동 과정 : M[1] 존재 → M[2] 존재  M[3] 존재   M[4] 존재 M[5] 미존재
  • M[1] = 5
  • M[5] = 6으로 갱신
  • 이런식으로 이동이 이루어지면, 연결된 모든 방 번호들을 확인해야 한다.
  • 1, 2, 3, 4, 5는 모두 사용된 방 번호이므로, 이후에 같은 방번호들이 나왔을 때 순차적으로 접근하지 않고 바로 6을 의미하게 하고 싶다.
  • 즉, M[1], M[2], M[3], M[4], M[5]의 값을 6이라는 루트 노드를 가진 집합으로 묶어야 한다.

 

 

 

1 → 2 → 3 → 4 → 5 → 6을 통해서 6을 얻는 것이 아니라, 1 ~ 5가 값으로 6을 가지고 있어야 한다. 따라서, Union-Find의 Find의 경로압축최적화가 필요하다.

 

 

 

 

## 해설코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
import java.lang.*;
import java.io.*;
 
class Solution {
    HashMap<Long, Long> hm = new HashMap<>();
    
    long find(long k){
        if(!hm.containsKey(k)){
            return k;
        }else{
// 경로 압축
            hm.put(k, find(hm.get(k)));
            return hm.get(k);
        }
    }
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        
        for(int i = 0; i < room_number.length; i++){
            long room = room_number[i];
            
            if(!hm.containsKey(room)){
                answer[i] = room;
                hm.put(room, find(room + 1));
            }else{
                long val = find(room);
                answer[i] = val;
                hm.put(val, find(val + 1));
            }         
        }
        
        return answer;
    }
}