문제 개요
열차의 도착 시간과 출발 시간 목록이 주어졌을 때, 어떤 열차도 역 안에서 대기하지 않고 바로 승강장에 진입할 수 있도록 하려면 철도역에 최소 몇 개의 플랫폼이 필요한지 구하는 문제입니다.
모든 시간 정보를 오름차순으로 정렬한 뒤 차례대로 살펴보면, "어떤 열차가 아직 역을 떠나지 않은 상태에서 새로운 열차가 도착했다"는 순간을 손쉽게 추적할 수 있어 문제를 간단하게 해결할 수 있습니다.
이 알고리즘의 시간 복잡도는 O(n log n)으로, 정렬에 드는 비용이 전체 성능을 좌우합니다.
입력 및 출력
입력:
도착 시간 목록과 출발 시간 목록
Arrival: {900, 940, 950, 1100, 1500, 1800}
Departure: {910, 1200, 1120, 1130, 1900, 2000}
출력:
필요한 최소 플랫폼 수: 3
알고리즘
입력 − 도착 시간 목록, 출발 시간 목록, 그리고 목록에 담긴 항목의 개수 n
출력 − 문제 해결에 필요한 최소 플랫폼 수
시작
도착 시간 목록과 출발 시간 목록을 각각 정렬한다
platform := 1, minPlatform := 1
i := 1, j := 0
i가 도착 목록을, j가 출발 목록을 가리키며 반복한다
if arrival[i] < departure[j] then
platform := platform + 1 // 새 열차 도착 → 플랫폼 하나 더 사용
i := i + 1
if platform > minPlatform then
minPlatform := platform
else
platform := platform - 1 // 열차 출발 → 플랫폼 하나 반환
j := j + 1
반복 종료
return minPlatform
끝
동작 원리
핵심은 투 포인터(two pointer) 기법입니다. 도착 배열을 가리키는 포인터 i와 출발 배열을 가리키는 포인터 j를 두고, 시간순으로 이벤트를 처리합니다.
- 다음 사건이 도착이라면(platform 증가): 현재 역에 머무는 열차가 하나 늘어난 것이므로 필요한 플랫폼 수를 1 늘리고, 지금까지의 최댓값과 비교해 갱신합니다.
- 다음 사건이 출발이라면(platform 감소): 한 열차가 떠나 플랫폼 하나가 비게 되므로 사용 중인 플랫폼 수를 1 줄입니다.
이 과정에서 기록된 platform 값의 최댓값이 곧 동시에 역에 머물러야 하는 열차 수의 최댓값, 즉 필요한 최소 플랫폼 수가 됩니다.
C++ 예제 코드
#include<iostream>
#include<algorithm>
using namespace std;
int minPlatform(int arrival[], int departure[], int n) {
sort(arrival, arrival+n); // 도착 시간 정렬
sort(departure, departure+n); // 출발 시간 정렬
int platform = 1, minPlatform = 1;
int i = 1, j = 0;
while (i < n && j < n) {
if (arrival[i] < departure[j]) {
platform++; // 열차 도착 → 플랫폼 추가
i++;
if (platform > minPlatform) // 최댓값이면 minPlatform 갱신
minPlatform = platform;
} else {
platform--; // 열차 출발 → 플랫폼 반환
j++;
}
}
return minPlatform;
}
int main() {
int arrival[] = {900, 940, 950, 1100, 1500, 1800};
int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
int n = 6;
cout << "필요한 최소 플랫폼 수: " << minPlatform(arrival, departure, n);
}
실행 결과
필요한 최소 플랫폼 수: 3
예제 풀이 과정
예제 데이터를 시간순으로 정렬하면 다음과 같습니다.
- 도착: 900, 940, 950, 1100, 1500, 1800
- 출발: 910, 1120, 1130, 1200, 1900, 2000
900에 첫 열차가 도착하고(플랫폼 1), 910에 출발해 플랫폼이 비지만, 940과 950에 연달아 두 열차가 도착하면서 1100~1120 구간에는 세 열차가 동시에 역에 머무르게 됩니다. 따라서 최소 3개의 플랫폼이 필요하다는 결과가 도출됩니다.