> 문제
2019 카카오 겨울 인턴십 문제
문제 : [호텔 방 배정]
> 문제풀이
union-find(disjoint set)로 풀었다. 문제풀다가 한번 나올때쯤 됐다했는데 딱 나왔다.
기존에 배열을 활용한 union-find는 제한사항에서 배열의 크기를(10^12) 수렴할 수 없기 때문에 Map을 활용하였다.
Map에 해당 값이 없으면 갱신해주고, 앞/뒤로 값이 있는지 체크해서, 큰값으로 union처리 해주었다.
값이 있다면 그보다 큰 값에 갱신해주고, 갱신한 값보다 큰값이 있는지 체크해서 union처리 해주었다.
import java.util.*;
class Solution {
static Map<Long, Long> memo;
static long find(long a){
if(memo.get(a) == null) return -1;
if(memo.get(a) == a) return a;
else {
memo.put(a, find(memo.get(a)));
return memo.get(a);
}
}
static void union(long a, long b){
long fa = find(a);
long fb = find(b);
if(fa < fb){
memo.put(a,fb);
}
}
public long[] solution(long k, long[] room_number) {
memo = new HashMap<>();
long[] answer = new long[room_number.length];
Long want, num;
for(int i=0; i<room_number.length; i++){
want = room_number[i];
num = find(want);
if(num == -1){
memo.put(want, want);
answer[i] = want;
if(find(want-1) != -1) union(want-1, want);
if(find(want+1) != -1) union(want, want+1);
}else{
memo.put(num+1, num+1);
answer[i] = num+1;
union(num, num+1);
if(find(num+2) != -1) union(num+1, num+2);
}
}
return answer;
}
}
문제 출처 : Programmers
PREVIOUS[프로그래머스] Level3 - 입국심사