[프로그래머스] kakao 2019 겨울 인턴십 / 호텔 방 배정 [JAVA]

문제링크 : programmers.co.kr/learn/courses/30/lessons/64063

코딩테스트 연습 - 호텔 방 배정

기본적인 생각으로 자신이 원하는 방이 없다면 그 방 번호보다 큰 것중 비어있는 방을 탐색하면서 배정하는 방식을 생각할 수 있다. k는 1 이상 10^12 이하인 자연수기 때문에 단순하게 배열로 해당 인덱스가 방이 배정 됐는지 아닌지 판단이 힘들다. 그래서 해시맵을 사용했다.

 

위 과정에서 문제점은 비어있는 방을 순차탐색 하는건 room_number가 20만이기 때문에 모든 값이 1일 때 

약 20만*(20만-1)/2의 시간이 걸린다. 따라서 다른 방법이 필요한데 union find(Disjoint Set)를 사용했다.

어떤 사람이 1번방을 배정 받았을 때 다음 1번방을 원하는 사람은 최소 2번방부터 조회하도록 하는 것이다.

그 다음 다시 1번방을 원할 때 3번을 조회하도록 한다. 

 

아래 setRoom 함수에서 재귀호출을 수행하며 다음 조회 번호를 리턴받아 경로압축을 위한 next를 리턴받는다.

재귀함수 수행 중 다음 조회 번호는 else 구문에서 방을 배정 해주며 다음 번호를 리턴하게된다. 

import java.util.*;
class Solution {
   public static long ans[];
    public static HashMap<Long,Long> hm =  new HashMap<>();
    public static long setRoom(int idx, long value){
        long ret = 0;
        if(hm.containsKey(value)){
            long ob = hm.get(value);
            long next = setRoom(idx,ob);
            hm.put(value,next);
            return next;
        }else{
            ans[idx] = value;
            hm.put(value,value+1);
            return value+1;
        }

    }

    public static long[] solution(long k, long[] room_number) {
        ans = new long[room_number.length];

        for(int i=0;i<room_number.length;i++){
            int idx = i;
            long value = room_number[i];
            setRoom(idx,value);
        }
        return ans;
    }
}