프로그래머스 문제 - 호텔 방 배정

프로그래머스 호텔 방 배정 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

호텔 투숙하려는 고객들에게 방을 배정해주어야 합니다.
고객들의 원하는 방 번호가 순서대로 주어지며, 처음의 각 방들을 전부 비워져있습니다.
순서대로 원하는 번호의 방을 배정해주며 이미 배정된 방일 경우 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
각 고객에게 배정되는 방 번호를 순서대로 배열에 담아주어야 합니다.

문제 풀이

원하는 방 번호로 배정시켜주면서 방에 들어갔다는 정보를 알고 있어야 됩니다.
방이 k값 만큼 주어지지만 k값으로 배열을 만들기에는 수가 너무 크기 때문에 배열을 사용하지는 못합니다.
또한 완전탐색을 하기에는 최대 20만개를 원소로 가지고 있기 때문에 탐색 또한 시간초과가 날 것입니다.
그러니 최대한 탐색량을 줄여야 합니다.

방에 들어갔다는 정보를 알아야 하기 때문에 어딘가에 저장을 해두어야 합니다.
그러니 배열같이 원하는 값의 정보를 빠르게 찾는 컨테이너인 hash자료구조(unordered_map)을 사용하였습니다.
key값은 현재 방 번호로, value값은 현재 방 번호를 찾는 사람이 가는 다음 방 번호로 저장해줍니다.

hash자료구조를 사용하여 차례대로 값이 존재하지 않을 시 현재 방 번호 : 현재 방 번호+1로 값을 저장해줍니다.
만약 값이 존재할 시 이미 그 방에 다른 사람이 배정되었다는 뜻이므로, value값의 방 번호를 확인해주며 값이 존재하지 않을 때까지 탐색해줍니다.

그렇게 나온 값들을 차레대로 배열에 넣어서 return해주면 답이 나옵니다.

이렇게만 해놓으면 반례가 있어 시간초과가 나올 것입니다. 그러니 재 방 번호를 찾는 사람이 가는 다음 방 번호인 value값을 갱신시켜주며 좀 더 빠르게 빈 방을 찾을 수 있도록 하는 것이 좋습니다.
값이 존재하여 value값을 찾을 때 이미 배정했던 방들의 번호를 다른 컨테이너에 따로 저장해줍니다.
이후 빈 방을 찾아 값을 저장해줄 때 다른 컨테이너에 저장된 값들도 찾아낸 빈 방 전까지 방이 비어있지 않다는 뜻이므로 value값을 찾아낸 빈 방+1값으로 갱신해주면 됩니다.
그렇게 되면 좀 더 빠르게 모든 탐색을 끝낼 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    unordered_map<long long, long long> room;
    queue<long long> q;
    
    unordered_map<long long, long long>::iterator iter;
    for(int i = 0; i < room_number.size(); i++)
    {
        long long curNumber = room_number[i];   //원하는 방 번호
        iter = room.find(curNumber);
        if(iter == room.end())  //원하는 방 번호가 배정되어있는지 확인
        {
            //없을 경우 방에 배정시켜준 후 map컨테이너에 (방 번호 : 대신 들어가야 하는 방 번호)식으로 저장해줌
            room.emplace(make_pair(curNumber, curNumber+1));
        }else
        {
            while(iter != room.end())   //있을 경우 value값을 보며 들어갈 방 검색
            {
                q.push(curNumber);  //지나온 방의 value값도 함께 바꿔주기 위해 queue에 저장
                curNumber = iter->second;
                iter = room.find(curNumber);
            }
            room.emplace(make_pair(curNumber, curNumber+1));    //빈 방을 map컨테이너에 저장해줌
            while(!q.empty())   //지나온 방들의 value값 갱신
            {
                long long cur = q.front();  q.pop();
                room[cur] = curNumber+1;
            }
        }
        answer.push_back(curNumber);
    }
    
    return answer;
}

출저

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