[틀림] [자바] 프로그래머스 호텔방배정 // 유니온파인드

https://school.programmers.co.kr/learn/courses/30/lessons/64063

프로그래머스

* 시도1

분포가 sparse하네? -> vis배열대신 map으로 방문체크 시도

 

빈방이아니면, while문에서 빈방을 찾을때까지 number++ 하는 방법

import java.util.*;

class Solution {
    static HashMap<Long,Integer> m = new HashMap<>();
    static ArrayList<Long> ret= new ArrayList<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = {};
        // System.out.println(m.get(0)); //null
        
        for(long number : room_number){
            if(m.get(number)==null){
                m.put(number,1);
                ret.add(number);
                continue;
            }
            while(m.get(number)!=null){
                number++;
            }
            m.put(number,1);
            ret.add(number);
        }
        
        answer = new long[ret.size()];
        for(int i=0;i<ret.size();++i){
            answer[i]=ret.get(i);
        }
        return answer;
    }
}

k가 10^12 이므로 시간초과가 난다. 알고리즘이 필요하다.

 

풀이

맵을 이용한 유니온 파인드를 사용해야한다.

유니온 파인드 알고리즘을 살펴보자.

1. parent배열을 둔다.

2. 부모가 없을때까지 들어간다.

3. 부모가 없다면 내부모 = 나 + 1 로 기록

4. 자신을 리턴

5. 나오면서 리턴된값 + 1 을 부모로 기록해놓기

유니온 파인드의 find 시간복잡도는 거의 상수시간이다.

코드만 보고 이해하기 쉽지 않아서, 그림을 그려보며 해봐야 한다.

import java.util.*;

class Solution {
    static HashMap<Long,Long> m = new HashMap<>();
    static ArrayList<Long> ret= new ArrayList<>();
    
    long find(long x){
        //방이 빈경우, 방번호+1을 다음방으로하고, 방번호 리턴
        if(m.get(x)==null){
            m.put(x,x+1);
            return x;
        }
        
        long nxt = find(m.get(x));
        m.put(x,nxt+1);
        return nxt;
    }
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = {};
        // System.out.println(m.get(0)); //null
        
        for(long number : room_number){
            long n = find(number);
            ret.add(n);
        }
        
        answer = new long[ret.size()];
        for(int i=0;i<ret.size();++i){
            answer[i]=ret.get(i);
        }
        return answer;
    }
}