문제
여러 기차 노선의 출발 시각표가 주어질 때, 목적지까지 M분이 걸리는 조건에서 N번째로 도착하는 기차의 노선 이름을 구하라.
입력
기차 노선 수 T, 소요 시간 M, N번째 기차, 그리고 각 노선의 이름과 출발 시각 목록이 주어진다.
출력
N번째로 도착하는 기차의 노선 이름을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 30 3 A 0 10 20 -1 B 5 15 25 -1 | B |
풀이
각 기차의 도착 시각을 계산하여 정렬한 뒤 N번째를 찾는다.
- 각 기차의 출발 시각에 M분을 더해 도착 시각을 계산한다 (60분 모듈러 적용)
- 모든 도착 시각을 오름차순으로 정렬한다
- 정렬된 목록에서 N번째(0-indexed로 N-1) 기차의 노선 이름을 출력한다
핵심 아이디어: 도착 시각 기준으로 정렬하면 N번째 도착 기차를 바로 찾을 수 있다. 순환 시각표이므로 모듈러 연산으로 정규화한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int t, n, m;
cin >> t >> m >> n;
string t_name;
int b_time;
vector<pair<int, string>> tt;
for (int i = 0; i < t; i++)
{
cin >> t_name >> b_time;
while (b_time != -1)
{
tt.push_back({(b_time + 60 - m) % 60, t_name});
cin >> b_time; // 시간 이름
}
}
auto cmp = [](auto a, auto b)
{ return a.first < b.first; };
sort(tt.begin(), tt.end(), cmp);
n -= 1;
n %= tt.size();
cout << tt[n].second;
return 0;
}복잡도
- 시간: O(N log N)
- 공간: O(N)