[ 프로그래머스 호텔 방 배정 (Lv4) ] (C++)

프로그래머스의 호텔 방 배정(Lv4) 문제이다.

[ 문제풀이 ]

접근 방법을 쉽게 생각하지 못해서 결국 다른 분들의 생각을 조금 참고해서 해결한 문제이다.

고객들이 원하는 방을 조건에 맞게 배정해 주어야 하는 문제이다.

이 문제를 구현할 때 핵심적으로 사용한 것은 2가지 이다.

1. STL map

2. Union - Find

먼저 방을 STL에서 제공해주는 map을 이용해서 관리해 주었다.

map은 간단하게 이야기해보면, 고유한 Key값과 그 Key값을 가지고 있는 Value값을 하나의 쌍으로 관리 하는 것이다.

여기서 '고유한 Key값'을 방 번호로 설정해 주었다.

예를 들어서 초기에 모든 방이 비어있는 상태에서, '1번방'을 원하는 손님이 나타났다고 생각해보자.

그럼 이 때, map에서 '1'이라는 값을 key값으로 가지는 원소가 존재하는지 판단하는 것이다.

현재는 모든 방이 비어있으므로, '1'이라는 값을 Key값으로 가지는 원소가 존재하지 않다는 것을 의미하고, map[1] = 0 이기 때문에, 그대로 방을 배정해 주면 된다.

그 이후에 또 한번 '1번방'을 원하는 손님이 나타났다고 생각해보자.

이 때는, map에서 '1'이라는 값을 key값으로 가지는 원소가 이미 존재하기 때문에 다른 방을 찾아야 할 것이다.

Union - Find를 이 과정에서 사용해 주었다. 사실 Union은 사용하지 않았고, 조건에 맞는 그 다음 방을 찾기 위해서 Find 하는 과정을 사용해 주었다.

예를 들어서, 'X번방'이 이미 꽉차서 다른 방을 찾아야 하는 경우라면, X + 1번방부터 탐색을 진행한다.

탐색의 종료조건은 위에서 선언해 놓은 map에서 '탐색하려는 방이 비어있으면' 종료해주었다.

말로 설명하니까 조금 어려워보이는데, 코드로 보면 굉장히 간단하다.

map<long long, long long> Room;
 
long long Find(long long N)
{
    if (Room[N] == 0) return N;
    return Room[N] = Find(Room[N]);
}

위의 과정이 빈방을 찾는 과정이다.

만약 "현재 탐색하려는 방이 비어있다면(line5)" 그 방의 번호를 return 해주고, 비어있지 않다면, 그 방에서 찾을 수 있는 비어있는 또 다른 방으로 탐색을 진행(line6) 해주었다.

이 과정을, 빈방일 때도, 빈방이 아닐때도 해주어야 한다.

왜냐하면 빈 방일 경우에는 그대로 손님을 방에 넣어준 후에, 그 다음번에 이 방을 원하는 손님이 나왔을 때를 생각해서 계산을 해놓는 것이다. 반대로, 빈 방이 아닐 때는 당연히 위의 과정을 통해서 빈 방을 찾아줘야 한다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
using namespace std;
 
map<long long, long long> Room;
 
long long Find(long long N)
{
    if (Room[N] == 0) return N;
    return Room[N] = Find(Room[N]);
}
 
vector<long long> solution(long long k, vector<long long> room_number)
{
    vector<long long> answer;
    for (int i = 0; i< room_number.size(); i++)
    {
        long long Num = room_number[i];
        if (Room[Num] == 0)
        {
            answer.push_back(Num);
            Room[Num] = Find(Num + 1);
        }
        else
        {
            long long Next_Num = Find(Num);
            answer.push_back(Next_Num);
            Room[Next_Num] = Find(Next_Num + 1);
        }
    }
    return answer;
}