[프로그래머스 2019 카카오 개발자 겨울 인턴십] 호텔 방 배정

programmers.co.kr/learn/courses/30/lessons/64063

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

와 너무 어렵다......... 풀이보고도 이해가 안갔다.

 

방 개수인 k가 작았더라면 쉽게 풀었겠지만 방 최대 수가 10^12로 배열로 선언할 수 없는 크기이다.

여기서 map을 떠올려야 했다.

 

그렇다면 map을 어떻게 사용해야 할까?

목적은 x보다 큰 값중 최소값을 찾는 것이다. 물론 전부 탐색해도 되지만 그러면 효율성이 매우 떨어진다.

이 때 필요한 것이 경로 단축을 위한 union find이다. 

 

1번방을 사용한다면 1번방의 다음 방인 2번방을 1번방의 부모로 연결시켜 놓는 것이다.

이렇게 되면 1번방을 찾는 손님은 자연스레 2번방을 배정받는다.

2번 방을 배정받은 후엔 다시 2번방을 3번방으로 연결시키고 2번방에 연결되어 있던 1번방 역시 3번으로 연결시킨다.

또 1번방을 찾는 손님은 어디로 갈까

1 -> 2-> 3번 방을 배정받고 3번방을 4번방에 연결 시킬 것이다.

 

이렇게 다음 배정받을 방을 부모 노드로 하는 union find를 적용한다.

코드를 작성하면 아래와 같다.

 

#include <string>
#include <vector>
#include <map>
#define ll long long

using namespace std;
map<ll, ll> m;

ll do_find(ll x){
    //아직 방이 비어있으면 원하는 방을 준다.
    if(m.find(x) == m.end()){
        return x;
    }
    
    //방이 없다면 번호보다 크면서 가장 가까운 방을 준다.
    return m[x] = do_find(m[x]);
}

// 경로 압축 x의 부모노드를 y로 만들기
void do_union(ll x, ll y){
    x = do_find(x);
    y = do_find(y);
    m[x] = y;
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    int len = room_number.size();
    for(int i=0; i<len; i++){
        ll checkin = do_find(room_number[i]);
        answer.push_back(checkin);
        do_union(checkin, checkin+1);
    }
   
    return answer;
}