(C++) - 2019 카카오 개발자 겨울 인턴십 : 호텔 방 배정

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

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

union find 문제였습니다.

 

풀이방법

이분탐색으로 시행하는 것을 생각할 수 있으나 요청한 방이 이미 있는 방에 경우 배정할 방을 정하기 어렵습니다. 2번방부터 10번방까지 다차있는 경우 2번방에 대한 요청이 들어왔을 때 11번방을 바로주지 못한다면 O(n)의 시간이 걸려 순차적으로 탐색해야하기 때문입니다. 또한 10^12로 k가 매우 크므로 배열로 방 번호를 잡을 수 없습니다. 따라서 map으로 해당방을 이미 이용하는지 아닌지를 알아보는 방법을 선택했습니다. 또한 대체로 줄 수 있는 방번호를 찾을 수 있는알고리즘으로 union - find를 선택했습니다. 주어진 방 번호에 대해 비어있는 방을 찾아 거슬러 올라가는 방식으로 구현할 수 있기 때문에 find함수를 이와 유사하게 사용할 수 있었습니다. 그래프를 union하지는 않기 때문에 union은 사용하지 않았습니다.

 

1. key : 요청된 방 번호, value : 줄 수 있는 방 번호로 설정해 map변수 roomMap을 선언합니다.

 

2. 고객이 원하는 방들을 순차적으로 탐색하며 다음을 시행합니다.

  2-1. 요청 방이 비었을 때 : value값이 0일 때를 의미하며 이 경우에는 바로 배정할 수 있으므로 answer에 해당 방번호를 push_back해줍니다. 그 후 해당 방을 이용하게 되었기 때문에 map의 상태도 갱신해줘야합니다. 조건에 따라 요청 방 번호 + 1를 find함수의 인자로 넘겨 비어 있는 방을 찾아 요청 방의 value값에 저장했습니다. 요청 방번호 + 1에 해당하는 방 또한 차 있을 수 있기 때문에 find함수로 빈방을 찾는 것입니다. 다음에 해당 번호의 방이 요청된다면 바로 빈 방을 줄 수 있도록 만들어주는 역할을 수행합니다. 또한 find함수를 수행하며 value값을 미리 갱신해주므로 매번 거슬러 올라가지 않고 바로 빈 방을 찾을 수 있도록 구현했습니다.

  

  2-2. 요청 방이 차있을 때 : 대체로 줄 수 있는 방 번호인 value또한 차 있을 수 있기 때문에 find(요청방의 value)로 대체 방이 줄 수 있는 빈 방을 찾습니다. 또한 거슬러 올라가며 갱신안된 value들을 수정해줍니다. 그 후 빈 방을 answer에 push_back 해줍니다. 이후 nroom이 요청되었을 떄 바로 빈 방을 줄 수 있도록 roomMap[nroom]을 find(해당 방번호 + 1)로 갱신 해줍니다.

 

3. answer를 반환해줍니다.

 

수행방식

입력 : [1]

빈 방

answer = {1}

roomMap[1] = 2 => { {1,2}, {2,0} }

 

입력 : [3]

빈 방

answer = {1, 3}

roomMap[3] = 4 => { {1,2}, {2,0}, {3,4}, {4,0} }

 

입력 : [4]

빈 방

answer = {1, 3, 4}

roomMap[4] = 5 => { {1,2}, {2,0}, {3,4}, {4,5}, {5,0} }

 

입력 : [1]

손님이 이미 있는 방

1이 요청되었을 때 차있으므로 비어있는 방을 찾습니다. find(roomMap[1]) = find(2) = 2

 

2가 줄 수 있는 방이 또 차있는 방일 수 있으므로 find(2)의 결과값을 저장합니다.

이 경우에는 2가 차있는 방이 아니므로 그대로 2가 반환됩니다.

answer = {1, 3, 4, 2}

roomMap[2] = find(3) = 4 => { {1,2}, {2,5}, {3,5}, {4,5}, {5,0} }

 

입력 : [3]

손님이 이미 있는 방

3이 차있는 방이므로 빈방을 찾습니다. find(roomMap[3]) = find(4) = 5

줄 수 있는 방이 4라고 되어있으나 4또한 이미 찬 방이기에 줄 수 있는 방 번호는 5입니다.

이후 줄 수 있는 방 번호들이 갱신됩니다.

answer = {1, 3, 4, 2, 5}

roomMap[5] = find(6) = 6 => { {1,2}, {2,5}, {3,5}, {4,5}, {5,6}, {6,0} }

입력 : [1]

손님이 이미 있는 방

같은 방식으로 1의 빈방을 찾습니다. find(roomMap[1]) = find(2) = 6

roomMap[6] = find(7) = 7 => { {1,2}, {2,6}, {3,5}, {4,5}, {5,6}, {6,7}, {7,0} }

Code

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
map <ll,ll> roomMap;
ll find(ll x){
    if(!roomMap[x]) return x; //방이 비어있다면 x를 배정해준다
    return roomMap[x] = find(roomMap[x]);
}
vector<ll> solution(ll k, vector<ll> room_number) {
    roomMap.clear();
    vector <ll> answer;
    for(auto room : room_number){
        if(!roomMap[room]){
            answer.push_back(room);
            roomMap[room] = find(room + 1);
        }
        else{
            ll nroom = find(roomMap[room]);
            answer.push_back(nroom);
            roomMap[nroom] = find(nroom + 1);
        }
    }
    return answer;
}