[프로그래머스] 호텔 방 배정

문제 :

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

제한 사항 :

• k는 1 이상 10^12 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.

풀이 방법 :

- 방 번호가 10^12이므로, 배열을 사용해 각 번호를 체크하는 풀이는 효율성을 통과할 수 없다.(메모리 초과)

   Map 사용은 생각을 했지만, Union-Find로 비어있는 가장 작은 방 번호를 배정하는 것은 생각하지 못했다.

 

2. 결국 힌트를 얻어서 해결.

 - 넘어온 방 번호가 맵에 없다면, 곧바로 Key로 배정을 해준다. 이 때, Value는 배정받은 번호의 다음 번호로 넣어준다. 

 - 만약, 넘어온 방 번호가 이미 배정을 받은 번호라면, Map에서 배정받은 Key와 쌍인 Value(다음 방 번호)에 배정을 해준다.

       -> find()에서 Value가 Map의 Key가 아닌 번호를 찾아 리턴한다. 그리고, 그 방 번호와 다음 번호를 쌍으로 다시 Map에 넣는다.

 

#include <string>
#include <vector>
#include <map>
using namespace std;
map<long long, long long> m;
 
long long find(long long num){
    if(m[num] == 0) return num;
    else {
        m[num] = find(m[num]);
        return m[num];
    }
}
 
vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    long long room_ok;
    long long room_next;
    for(int i = 0; i < room_number.size(); i++){
        room_ok = room_number[i];
        if(m.count(room_ok) == 0){
            answer.push_back(room_ok);
            m[room_ok] = find(room_ok+1);
        }
        else{
            room_next = find(room_ok);
            answer.push_back(room_next);
            m[room_next] = find(room_next + 1);
        } 
    }
    return answer;
}