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

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 Set과 Map을 이용해서 이미 배정된 적이 있는 방 번호라면 바로 다음 방을 찾도록 하면 해결될 것이라는 생각이 들었던 문제다.

 

Set에는 이미 배정받은 방들의 수를 저장하고, Map에는 [배정받길 원하는 방 : 다음에 실제로 배정받을 방]의 구조로 저장한다.

 

처음에 특정 방을 배정받고 싶을 때, 그 방이 Map에 없으면 첫 방문이다.

그러므로 원하는 방에 해당하는 숫자를 가져온다.

 

만약 Map에 있다면 첫 방문이 아니므로 이미 Map에 저장된 수를 가져온다.

이후 가져온 숫자가 Set에 있으면, 이미 배정받은 방이므로 Map에서 그 숫자가 다음에 실제로 배정받을 방의 숫자를 가져온다.

 

이 과정을 While문으로 반복을 하면서 빈 방이 나올 때 까지 반복한다.

 

하지만 처음에는 이렇게 풀었을 때 효율성 풀이를 통과하지 못했다.

 

그래서 방법을 고민하다가 while문에서 거쳐온 방들도 배정받아야 할 방의 숫자가 변경되므로 이를 기록했다가 업데이트를 해주는 방법으로 코드를 추가했다.

 

빈 방이 나온다면, 방을 배정받을 수 있으므로 방을 배정하고 지금까지 배정을 받을 수 있는지 확인을 거쳐온 방들도 다음에 방문할 방을 업데이트 해주면 된다.

 

하지만 이렇게 풀었을 때도 효율성 풀이를 통과하지 못했다.

 

왜 통과하지 못하는지 고민을 했더니 거쳐온 방들을 업데이트 하는 과정에서 시간이 증가하기 때문인 것 같았다.

 

그래서 다른 사람들이 어떻게 풀었는지 질문을 보는데, unordered_map을 사용하면 좀 더 빨라서 통과가 된다는 글을 보고 unordered map으로 바꿨더니 풀렸다...

 

+ Set에서 Map에 키가 없다면 int로 0을 반환 하므로 이를 이용해 배정 받은 적이 있는지 체크하는 방법도 있다.

 

​

[아이디어 정리]

1. Set을 이용해 이미 방을 배정받았는지 확인하고, Map을 이용해 다음에 어떤 방을 방문할지 빠르게 찾는다.
2. 만약 Map에서 가리키는 배정받을 방이 이미 배정된 방 A라면, Map에서 A가 다음에 방문할 방을 Set에서 확인한다.

while문으로 루프를 돌리다가 배정을 받은 적이 없는 방이 나오면 while문을 종료하고 지금까지 방문했던 방 들이 다음에 배정받을 방들을 전부 update해준다.

 

Code

 

 

#include <string>
#include <vector>
#include <unordered_map> 
#include <set>
using namespace std;

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer(room_number.size());
    set<long long>roomSet;
    unordered_map<long long, long long>roomMap;
    long long findRoomNum;
    for(int i=0; i<room_number.size(); i++)
    {
        vector<long long> temp;        
        if (roomMap[room_number[i]]==0)
        {
            findRoomNum=room_number[i];
        }
        else
        {
            findRoomNum=roomMap[room_number[i]];
        }
        temp.push_back(findRoomNum);
        while(roomSet.find(findRoomNum)!=roomSet.end())
        {
            findRoomNum=roomMap[findRoomNum];
            temp.push_back(findRoomNum);
        }
        answer[i]=findRoomNum;
        roomSet.insert(findRoomNum);
        roomMap[findRoomNum]=findRoomNum+1;
        for (int i=0; i<temp.size(); i++)
        {
            roomMap[temp[i]]=findRoomNum+1;            
        }
        roomMap[room_number[i]]=findRoomNum+1;        
    }
    return answer;
}

 

---

 

문제를 풀고 중간에 방을 update하는 과정에 대해 시간복잡도를 생각해봤는데 어떤 시간복잡도를 가지는지 잘 모르겠다.

방을 방문한 개수에 따라 시간복잡도가 달라지는데, 중간에 업데이트를 하고나면 업데이트를 한 방들의 수인 n개 만큼 중간 과정이 사라져서 O(N^2)보다 짧을 것 같은데... 어렵네;;

 

프로그래머스