문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
고객은 투숙하기 원하는 방 번호를 제출합니다.
고객이 원하는 방이 비어 있다면 즉시 배정합니다.
고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.
원하는 방 번호 배정된 방 번호
1 1
3 3
4 4
1 2
3 5
1 6
제한 사항
k는 1 이상 1012 이하인 자연수입니다.
room_number 배열의 크기는 1 이상 200,000 이하입니다.
room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.
문제 풀이
상당히 어려웠던 문제였다. 처음에 python으로 단순히 list pop과 순차로 하니 효율성 부분을 통과하지 못했다.
제한 사항에서 많은 범위가 나온 것을 보아 효율적인 탐색을 해야하고, 방을 배정받지 못하는 고객은 발생하지 않는다 는 부분이 중요했다.
위의 제한 사항을 다시 생각하자면 투숙객은 원하는 방에 들어가거나, 원하는 방보다 크며 비어있는 방 중 가장 번호가 작은 방에 투숙하게 된다.
당연한거 아니야? 라고 생각할 수 있지만 저렇게 하나 하나 확실한 경우를 생각하는 것이 좋다.
어김없이 직접 해보는 시간을 가지는데, 1이 들어가면 1에 아무도 없는지 확인하고 없으면 들어간다. 만약 이후에 1을 누군가 원한다면, 원하는 방보다 크며 비어있는 방 중 가장 번호가 작은 방에 투숙하면 된다.
방이 차있으면 다른 방을 탐색할 때, x+1번 방부터 탐색을 진행해서 탐색하려는 방이 비어 잇으면 종료해준다.
#include <string>
#include <vector>
#include <map>
using namespace std;
map<long long , long long> R;
long long Find (long long n)
{
//탐색하는 방이 비어있으면 방을 return;
if(R[n] == 0) return n;
//탐색하는 방이 차있으면 빈 방이 있을때 까지 찾아줌.
else return R[n] = Find(R[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 (R[Num] == 0)
{
answer.push_back(Num);
//Num +1은 본인보다 큰 방 중에 선택해야하기 때문임.
R[Num] = Find(Num+1);
}
else{
long long Next_Num = Find(Num);
answer.push_back(Next_Num);
R[Next_Num] = Find(Next_Num+1);
}
}
return answer;
}