[Programmers] 호텔 방 배정

이 문제는 간단해 보이나 효율성을 통과하기 어려운 문제이다.

일반적인 풀이방법으로는 정확성은 통과할 수 있지만 유니온파인드 알고리즘을 사용하지 않는다면 효율성을 통과하기 어렵다. 또한, 유니온 파인드라는 것을 사용한다 하더라도 K값이 상당히 큼(10^12)으로 일차원 배열을 사용하기 어렵다. 따라서 필요한 것에 대해서만 HashMap의 형태로 유니온파인드를 사용해야한다. 

이 문제는 다음과 같은 로직을 적용하였다.
1. room_number의 수를 전체 하나씩 보기
2-1. 수가 hashMap에 존재하지 않는 key이거나 (수,수) 의 형태로 존재한다면 현재 key를 배정
2-2. 그렇지 않다면 find(map.get(key))를 하여 새로운 방을 배정
3. 마지막으로 현재수와 현재수+1을 union

아이디어를 생각하기 어려웠을 뿐 아니라 구현도 생각보다 어려워서 도움을 받은 풀이이다. 유니온파인드와 관련된 연습이 필요한 것 같다.

package programmers;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
 
public class Solution_2019카카오겨울_호텔방배정 {
    
    
    public static void main(String[] args) {
        int k=10;
        long[] room_number= {1,3,4,1,3,1};
        
        long[] answer=solution(k, room_number);
        
        for(long a : answer)
            System.out.print(a+" " );
    }
 
    static Map<Long,Long> map;
    
    static long[] solution(long k, long[] room_number) {
        int n = room_number.length;
        long[] answer = new long[n];
        map = new HashMap<Long, Long>();
 
        for(int i=0;i<n;i++) {
            answer[i]=find(room_number[i]);    
            union(answer[i],answer[i]+1);    //현재수와 다음수를 union
        }
        
        return answer;
    }
    
    static long find(long num) {
        if(!map.containsKey(num) || map.get(num)==num) {
            map.put(num, num);
            return num;
        }
        
        map.put(num, find(map.get(num)));
        return map.get(num);
    }
    
    static void union(long num1,long num2) {
        num1=find(num1);
        num2=find(num2);
        
        if(num1<num2)
            map.put(num1, num2);    //더큰 것으로
        else
            map.put(num2, num1);
        
    }
}