## 접근
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;
}
}
|
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[2020 카카오 인턴십] 보석 쇼핑 (0) | 2020.09.09 |
---|---|
[2020 카카오 인턴십] 수식 최대화(Java, 문자열 처리, ArrayList For문 내 원소 삭제) (0) | 2020.09.07 |
[2019 카카오 개발자 겨울 인턴십] 불량 사용자 (0) | 2020.08.31 |
[2019 카카오 개발자 겨울 인턴십] 튜플(Java, 깊은 복사, 문자열 처리) (0) | 2020.08.29 |
[2019 KAKAO BLIND RECRUITMENT] 블록 게임(Java, 간단한 코드) (0) | 2020.08.27 |