[카카오 기출] 호텔 방 배정 풀이

알고리즘

Union-find

풀이 과정

• 1 ≤ k ≤ 10^12 이하이므로 long 으로 자료형을 설정한다.
• 주의사항 : 배열 같은 경우, index를 long으로 설정하지 못한다. → Map 자료구조 관리하여야 한다.
• 어려웠던 점 : parent를 찾을 때 일반적으로 배열을 사용했는데 map 자료구조를 떠올려야 했다.
• 시간초과 난 부분
  • 맨 처음에 Map을 parent[i] = i 와 같은 식으로 k범위 까지 초기화 시켜줬는데, 시간초과 난다.
• parent를 계속 갱신 시켜주며, 가장 가까운 호텔을 parent로 다시 갱신한다.

코드

import java.util.*;
class Solution {
    public Map<Long, Long> parent = new HashMap<>();
    public long findParent(long ori, long a) {
        if (parent.get(a) == null) {
            parent.put(a, a+1);
            return a;
        }
        parent.put(a, findParent(ori, parent.get(a)));
        return parent.get(a);
    }
   
    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 num = room_number[i];
            long par = findParent(num, num);
            answer[i] = par;
        }
        
        return answer;
    }
}