C++로 풀어보는 회전문(Revolving Door) 스케줄링 문제

요청 목록이 주어진다고 가정해 봅시다. 여기서 requests[i]는 [t, d] 형태를 가지며, 시간 t에 한 사람이 문에 도착했고, 그 사람이 안으로 들어가려는지(1로 표시) 아니면 밖으로 나가려는지(0으로 표시)를 의미합니다.

문은 하나뿐이고, 문을 사용하는 데는 1시간 단위가 걸립니다. 이때 다음과 같은 규칙을 따라야 합니다.

문은 '안(in)' 상태로 시작하며, 이후에는 마지막 사용자가 사용한 방향으로 설정됩니다.
특정 시간 t에 문 앞에 사람이 한 명만 있다면, 그 사람이 곧바로 문을 사용할 수 있습니다.
두 명 이상이 동시에 문을 기다리고 있다면, 먼저 도착한 사람이 우선권을 가지며, 이후에는 이전에 사용된 방향이 우선합니다.
1시간 단위 동안 아무도 문을 사용하지 않으면, 문은 초기 상태('in')로 되돌아갑니다.

우리가 구해야 하는 것은 각 요소가 [t, d] 형태로, 시간 t에 사람이 실제로 안으로 들어갔는지 밖으로 나갔는지를 나타내는 정렬된 리스트입니다.

예를 들어 입력이 [[2,0],[3,1],[6,0],[6,1],[3,0]]이라면, 출력은 [[2,0],[3,0],[4,1],[6,1],[7,0]]이 됩니다.

문제 해결 접근 방식

이 문제를 해결하기 위해 다음 단계를 따릅니다.

배열 v를 정렬합니다.
결과를 담을 리스트 ret을 생성합니다.
curr := 1, i := 0, j := 0으로 초기화합니다.
n := v의 크기로 설정합니다.
i < n인 동안 다음을 반복합니다.
- ret이 비어 있지 않고, v[i][0]에서 ret의 마지막 요소의 시간을 뺀 값이 1보다 크면 curr := 1로 초기화합니다. (문이 초기 상태로 돌아간 경우)
- j := i + 1로 설정합니다.
- 크기가 2인 배열 arr을 정의합니다.
- arr[v[i][1]] 값을 1 증가시킵니다.
- j < n이고 v[j][0]이 v[i][0]과 같은 동안 arr[v[j][1]] 값을 1씩 증가시킵니다. (같은 시간에 도착한 사람들을 그룹화)
- t := max(ret이 비어 있으면 0, 아니면 ret의 마지막 요소의 t + 1)와 v[i][0] 중 최댓값으로 설정합니다.
- arr[1]과 arr[0]이 모두 0이 아니라면:
  - arr[curr]이 0이 될 때까지 매 단계마다 1씩 감소시키며, {t, curr}를 ret의 끝에 삽입하고 t를 1 증가시킵니다.
  - curr := curr XOR 1로 방향을 전환합니다.
  - arr[curr]이 0이 될 때까지 같은 방식으로 반복합니다.
- 그렇지 않으면:
  - curr := v[i][1]로 설정합니다.
  - arr[curr]이 0이 될 때까지 {t, curr}를 ret에 삽입하고 t를 1씩 증가시킵니다.
- curr := ret의 마지막 요소의 방향으로 갱신합니다.
- i := j로 설정합니다.
ret을 반환합니다.

C++ 구현 예제

더 나은 이해를 위해 다음 구현 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << "[";
      for (int j = 0; j < v[i].size(); j++) {
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}
class Solution {
   public:
   vector<vector<int>> solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end());
      vector < vector <int > > ret;
      int curr = 1;
      int i = 0;
      int j = 0;
      int n = v.size();
      while(i < n){
         if(!ret.empty() && v[i][0] - ret.back()[0] > 1){
            curr = 1;
         }
         j = i + 1;
         vector <int> arr(2);
         arr[v[i][1]]++;
         while(j < n && v[j][0] == v[i][0]){
            arr[v[j][1]]++;
            j++;
         }
         int t = max((ret.empty()? 0 : ret.back()[0] + 1), v[i][0]);
         if(arr[1] && arr[0]){
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
            curr = curr ^ 1;
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }else{
            curr = v[i][1];
            while(arr[curr]--){
               ret.push_back({t, curr});
               t++;
            }
         }
         curr = ret.back()[1];
         i = j;
      }
      return ret;
   }
};
int main(){
   vector<vector<int>> v = {{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}};
   Solution ob;
   print_vector(ob.solve(v));
}

입력

{{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}}

출력

[[2, 0],[3, 0],[4, 1],[6, 1],[7, 0]]

이 알고리즘은 입력 배열을 정렬한 후, 같은 시간에 도착한 요청들을 그룹으로 묶어 처리합니다. 양방향 대기자가 모두 존재하는 경우에는 이전 방향의 대기자를 먼저 통과시키고, 한쪽 방향만 존재하는 경우에는 해당 방향의 대기자를 모두 처리한 뒤 다음 그룹으로 넘어갑니다. 이러한 방식으로 각 사람이 실제로 문을 통과하는 시점을 정확하게 계산할 수 있습니다.