C++로 구현하는 기차역 최소 플랫폼 수 계산 알고리즘

문제 정의

기차역에 도착하는 모든 열차의 도착 시간과 출발 시간이 주어졌을 때, 어떤 열차도 대기하지 않고 바로 진입할 수 있도록 하기 위해 필요한 최소 플랫폼 수를 구하는 문제입니다.

입력으로는 열차의 도착 시간과 출발 시간을 각각 담고 있는 두 개의 배열이 제공됩니다.

아래 입력 예시의 경우 최소 3개의 플랫폼이 필요합니다.

알고리즘

1. 도착 시간 배열과 출발 시간 배열을 각각 오름차순으로 정렬한다.
2. 도착했지만 아직 출발하지 않은 열차의 수를 실시간으로 추적하며,
   동시에 역에 머무는 열차 수의 최댓값을 구한다.

동작 원리

두 배열을 정렬한 뒤 투 포인터(two pointer) 기법으로 도착 이벤트와 출발 이벤트를 시간순으로 비교합니다. 다음 열차의 도착 시간이 현재 가장 빠른 출발 시간보다 빠르거나 같다면, 기존 열차가 아직 떠나지 않은 상태에서 새 열차가 들어오는 것이므로 필요한 플랫폼 수를 하나 늘립니다. 반대로 출발 시간이 더 빠르면 한 열차가 떠나는 것이므로 플랫폼 수를 하나 줄입니다. 이 과정 전반에서 기록된 동시 대기 열차 수의 최댓값이 곧 필요한 최소 플랫폼 수가 됩니다.

이 알고리즘의 시간 복잡도는 정렬 단계가 지배적이므로 O(n log n)이며, 추가적인 자료 구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

구현 예제

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getPlatformCount(int *arrival, int *departure, int n){
   sort(arrival, arrival + n);
   sort(departure, departure + n);
   int platformCnt = 1;
   int result = 1;
   int i = 1;
   int j = 0;
   while (i < n && j < n) {
      if (arrival[i] <= departure[j]) {
         ++platformCnt;
         ++i;
         if (platformCnt > result) {
            result = platformCnt;
         }
      } else {
         --platformCnt;
         ++j;
      }
   }
   return result;
}
int main()
{
   int arrival[] = {900, 935, 940, 1100, 1430, 1800};
   int departure[] = {915, 1145, 1105, 1200, 1815, 1900};
   cout << "Minimum required platforms = " <<
   getPlatformCount(arrival, departure, SIZE(arrival)) << endl;
   return 0;
}

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Minimum required platforms = 3