호텔 방 배정

Description

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
고객은 투숙하기 원하는 방 번호를 제출합니다.
고객이 원하는 방이 비어 있다면 즉시 배정합니다.
고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.
원하는 방 번호 배정된 방 번호
1 1
3 3
4 4
1 2
3 5
1 6
전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]
k는 1 이상 1012 이하인 자연수입니다.
room_number 배열의 크기는 1 이상 200,000 이하입니다.
room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

Example

[입출력 예]
k = 10
room_number = [1,3,4,1,3,1]
result = [1,3,4,2,5,6]

입출력 예에 대한 설명
입출력 예 #1
문제의 예시와 같습니다.
첫 번째 ~ 세 번째 고객까지는 원하는 방이 비어 있으므로 즉시 배정받을 수 있습니다. 네 번째 고객의 경우 1번 방을 배정받기를 원했는데, 1번 방은 빈 방이 아니므로, 1번 보다 번호가 크고 비어 있는 방 중에서 가장 번호가 작은 방을 배정해야 합니다. 1번 보다 번호가 크면서 비어있는 방은 [2번, 5번, 6번...] 방이며, 이중 가장 번호가 작은 방은 2번 방입니다. 따라서 네 번째 고객은 2번 방을 배정받습니다. 마찬가지로 5, 6번째 고객은 각각 5번, 6번 방을 배정받게 됩니다.

Code

#include <bits/stdc++.h>

using namespace std;

long long find(map<long long, long long> & room_check, long long room_number)
{
    if(room_check[room_check[room_number]]){
        room_check[room_number] = find(room_check, room_check[room_number]);
        return room_check[room_number];
    }
    else{
        room_check[room_check[room_number]] = room_check[room_number] + 1;
        return room_check[room_number];
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    int size = room_number.size();
    vector<long long> answer (size, 0);
    map<long long, long long> room_check;
    for(int i=0; i<size; i++){
        if(!room_check[room_number[i]]){ // 빈 방
            room_check[room_number[i]] = room_number[i]+1; // next room
            answer[i] = room_number[i];
        }
        else{
            answer[i] = find(room_check, room_number[i]);
        }
    }

    return answer;
}

Thoughts

본 문제는 2019 카카오 겨울 인턴십에 출제된 문제로, 문제를 푸는 법은 다양하게 존재할 수 있으나 효율성을 통과하기위해 생각을 해봐야했던 문제이다.
Hash map을 이용하여 각 방의 번호와 예약가능 여부를 체크하는 식으로 생각하며, 사람들이 원하는 방의 번호를 순서대로 담고있는 vector<int> room_number를 순서대로 조회하며 원하는 방이 예약이 가능하면 Hash map 저장, 안되면 그 다음 방부터 순서대로 조회하여 가능한 가장 작은 수의 방을 찾는 식으로 하면 정확도 기준은 통과할 수 있지만 효율성이 떨어진다. room_number가 매우 커지는 상황을 생각하면 원하는 방이 예약이 안될 때 다시 조회하는 일이 상당히 비효율적인 일이라는 것을 바로 알아차릴 수 있었고, 곧바로 새로운 아이디어가 필요했다.

그리고 이번 문제를 풀면서 다시 한 번 공부하게된 알고리즘 Union-find. union-find알고리즘을 사용하면 위와 같은 비효율성을 개선할 수 있다. 서로 다른 중복되지 않은 n개의 원소가 있을 때, 서로 간의 연결된 구성 속에서 노드간의 연결성을 확인하거나 서로 다른 두 원소간의 연결을 합치는 조작 등에서 사용되는 알고리즘이자 자료구조라고 할 수 있는데, 알고리즘을 공부하면서 배웠지만 자주 사용하고 생각하지 않으니 잘 떠오르지 않았었다.
구현하는 방법도 여러가지 이며, 배열을 이용하여 구현할 수도 있고 Tree(Graph)를 사용하여 구현할 수도 있다.

우선 주어진 위 문제에서 어떻게 union-find를 이용해서 문제를 해결할 수 있는지 살펴 보자.
room_number 배열을 순회하면서 우리는 각자 원하는 방의 번호를 갖게되는데, 이 때 기존의 예약 가능 여부를 갖고 있는 Hash map을 통해서 예약할 방이 원하는 방번호가 되는지 안되는지 알 수 있다.
만약 원하는 방번호가 1번이고 1번 방이 예약이 된는 방이라면 1번방은 이제 그다음에 원하는 사람이 나타나도 1번에 예약을 할 수없고 2번부터 예약할 수 있다. 따라서 1번방은 -> 2번방을 가리키는 관계라고 이해할 수 있다.
만약 다음으로 1번방을 원하는 사람이 나타나면 1->2 를 가리키고 있으므로 2번방을 예약하게 되고, 1->3을 가리키게 하면 된다.
이와 같은 방법으로 순서대로 room_number를 순회하면서 나타나는 방번호들의 관계를 Union-find형태로 구현하면 효율성과 정확도 모두 해결할 수 있는 풀이가 된다. => [원하는 방 번호] -> [사실상 예약할 수있는 그 다음 방번호]

정리하자면, 위 문제는 모두 효율성을 어떻게 통과했을지가 관건인 문제였다. 문제의 상황을 이해하고, 그 상황에 적합한 자료구조와 알고리즘을 생각해서 구현할 수 있는가를 물어보는 기본적인 알고리즘문제의 틀에서 다를게 없지만, 문제를 읽고 이렇게 실전에서 풀 수 있도록 하려면 튼튼한 자료구조의 이해와 기본 원칙에 대한 공부, 구현에 대한 능숙함 이런 기본기가 갖춰져야 함을 알 수 있다.