문제설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

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

한 번에 한 명씩 신청한 순서대로 방을 배정합니다. 고객은 투숙하기 원하는 방 번호를 제출합니다. 고객이 원하는 방이 비어 있다면 즉시 배정합니다. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다. 예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호
1,3,4,1,3,1

배정 받은 방 번호
1,3,4,2,5,6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 사항

  • k는 1 이상 1012 이하인 자연수입니다.
  • room_number 배열의 크기는 1 이상 200,000 이하입니다.
  • room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
  • room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
    • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

예제

k             10        
room_number   [1,1,1,1,1,1,1,1,1]
result        [1,2,3,4,5,6,7,8,9]

접근

  • k의 범위가 매우 크다. 브루트 포스로는 절대 안 된다.
  • 중복되는 방 번호를 받았을 때 들어가야 할 방을 미리 알 수 있다면…?

내가 생각한 풀이

  • Union-Find를 통해 방이 배정된 경우 부모를 미리 알아놓도록 하자. 그래서 배정 될 경우 그 부모에 배정을 시키면 된다.

코드

#include <string>
#include <vector>
#include <map>
using namespace std;

map<long long, long long> parent;

long long find(long long u)
{
  if(u == parent[u]) return u;
  return parent[u] = find(parent[u]);
}
void merge(long long u, long long v)
{
  u = find(u); v = find(v);
  if(u == v) return;
  parent[v] = u;
}

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++)
  {
      if(parent.find(room_number[i]) == parent.end()) //방이 비었을 경우 그냥 넣어준다.
      {
          parent.insert({room_number[i], room_number[i]});
          answer.push_back(room_number[i]);
          //방의 앞 뒤를 살펴서 방들이 존재할 경우 부모를 업데이트 시켜준다.
          if(parent.find(room_number[i] - 1) != parent.end())
          {
              merge(room_number[i], room_number[i] - 1);
          }
          if(parent.find(room_number[i] + 1) != parent.end())
          {
              merge(room_number[i] + 1, room_number[i]);
          }
      }
      else
      {
          long long temp = find(room_number[i]); //중복되는 방이 갖는 부모를 찾는다.
          parent.insert({temp + 1, temp + 1});
          answer.push_back(temp + 1);
          //방이 중복 된다는 의미는 앞에 방이 무조건 존재 하므로 부모를 업데이트 시킨다.
          merge(temp + 1, temp);
          //마찬가지로 새로 배정된 방 뒤에 방이 있는지 확인하고 부모를 업데이트 시킨다.
          if(parent.find(temp + 2) != parent.end())
          {
              merge(temp + 2, temp + 1);
          }
      }
  }
  return answer;
}

생각하지 못한 점

  • 다른 사람의 코드를 보니 union없이 find로만 코드를 구현했다. 훨씬 간단하게 구현할 수 있었는데 내가 더 복잡하게 생각했다는 의미이다.
  • 처음에 이분탐색으로 접근했었다. 이분탐색을 통해 방이 존재하지 않으면서 room_number보다 큰 경우를 찾으면 되지 않을까 했는데 이분 탐색으로 찾지 못하는 부분이 존재했다. 따라서 이분탐색은 틀린 접근이라는 결론을 내렸다.