한 노선에 완전히 포함되는 노선은 제외하므로 솔루션은 구간을 검사하는 스위핑에 근간을 두고 있다.
버스 정류장이 원형으로 연결되어 있으므로 각 케이스에 대한 전략과 그 구현이 복잡해진다.
Step 1.
문제 접근을 용이하게 하기 위해 각 버스 노선을 두 종류로 분리해보자.
1. 0 을 중간점으로 경유하지 않는 노선 line
2. 0 을 중간점으로 경유하는 노선 circle
1번의 경우 버스 노선이 직선으로 생겼다고 취급해도 된다.
2번의 경우 버스 노선이 N - 1이하의 시작점에서 0번 정류소를 지나가는 형태이다.
Step 2.
이 두 종류의 노선에서 3가지의 경우의 수를 통해 어떤 것을 구해야 하는지 파악해보자.
1. line과 line의 비교
line 과 line의 비교는 단순한 스위핑을 수행하면 된다. 노선 a와 노선 b가 있을 때
$ (a.start \leq b.start) \wedge (b.end \leq a.end) $ 이면 노선 b는 a에 포함되므로 b를 배제시키면 되겠다.
2. circle과 circle의 비교
ciecle과 circle은 0을 기준으로 두 부분으로 나눠 각 부분을 확인할 수도 있지만 전처리를 통해 1번처럼 처리할 수 있다.
바로 끝나는 지점에 N만큼 더해 길이가 2N인 직선 노선으로 변환하게 되면 1번처럼 스위핑을 수행할 수 있다.
이렇게 해줘도 결과적으로 노선의 길이는 같음을 직접 계산해보면서 알 수 있다.
예제 입력에 있는 5 0과 9 4를 예로 들면
N인 10씩 더했을 때 5 10 과 9 14가 되므로 이를 비교했을 때 둘 중 하나가 나머지를 포함하지 않으므로 어느 것 하나 철거하지 않아도 된다. (당장 이 두개만 놓고 본다면)
여기서 5 8 이 추가된다고 해보자. 그러면 5 8은 5 10에 포함되므로 5 8은 배제된다.
3. line과 circle의 비교
line은 0이상에만 노선이 있고 circle은 0이전에 노선이 존재함을 유의하자.
즉 우리가 고려해야 할 것은 line의 종착점이 circle의 종착점보다 작거나 같은지 확인하기만 하면 된다. 만약 그렇다면 해당 line이 circle에 포함된다는 사실을 직관적으로 알아챌 수 있다.
그렇다면 circle의 종착점 어떤 것을 기준으로 잡아야 할까? circle의 종착점 중 가장 긴 것으로 설정하기만 하면 된다.
그 어떤 line도 가장 멀리 있는 종착점을 가진 circle을 넘지 못하면 바로 포함되는 것이기 때문이다!
이렇게 3가지 케이스에 대해 스위핑을 수행하면 시간 복잡도 $O(MlgM)$으로 답을 구할 수 있다.
구현
솔루션은 이해하기 어렵지는 않다. 하지만 그 구현이 복잡하기에 잘 풀지 못하겠다면 AC를 받은 코드를 보는 것이 도움이 될 것이다.
for문을 통해 데이터를 입력받으면서 circle 종착점의 최댓값 circlemax를 찾고 전처리를 하도록 한다.
노선에 대한 정렬은 시작점 오름차순, 종착점 내림차순으로 정렬한다.
그 이유는 정렬되었을 때를 기준 i + 1번째 노선이 i번째 노선에 포함되는지 선형적으로 검사할 수 있기 때문이다.
정렬 후 $O(n)$스위핑을 수행한다. 노선이 line일 때 circlemax 범위에 포함되는지 그 외 마지막으로 통과한 노선에 포함되는지 스위핑을 통해 답을 추려낸다.
전체 코드 : 주석을 달았다.
#include <bits/stdc++.h>
using namespace std;
vector<int> res;
// 노선 정렬 비교 함수
bool cmp(vector<int> &l, vector<int> &r)
{
if (l[0] == r[0])
return l[1] > r[1];
return l[0] < r[0];
}
// 작은 번호부터 출력하기 위한 정렬 비교 함수
bool cmpnum(vector<int> &l, vector<int> &r) { return l[2] < r[2]; }
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> v(m, vector<int>(3));
int circlemax = 0;
for (int i = 0; i < m; ++i)
{
cin >> v[i][0] >> v[i][1];
// 노선의 종류가 circle이라면
if (v[i][0] > v[i][1])
{
// circle이 가질 수 있는 종착점의 최댓값을 찾는다.
circlemax = max(circlemax, v[i][1]);
// 스위핑 전처리를 위해 n을 더해준다.
v[i][1] += n;
}
v[i][2] = i + 1;
}
sort(v.begin(), v.end(), cmp);
vector<vector<int>> res;
for (int j = 0; j < m; ++j)
{
// 3번 경우에 대해 검사하는 조건문이다. (line과 circle)
// 해당 노선이 circlemax 범위 안에 포함되는가? 그렇다면 답이 될 수 없다.
// circle의 경우는 이미 n을 더했으므로 이 조건문에 걸리지 않는다.
if (v[j][1] <= circlemax)
continue;
// 어떤 노선에 포함되지 않는가?
// 시작점은 오름차순 정렬된 상태이므로 비교하지 않아도 된다. 종착점만 비교하여 걸러낸다.
if (res.empty() || (res.size() && res.back()[1] < v[j][1]))
res.push_back(v[j]);
}
sort(res.begin(), res.end(), cmpnum);
for (auto &t : res)
cout << t[2] << ' ';
}
'백준 > 스위핑' 카테고리의 다른 글
백준 22876 - 츠바메가에시 (0) | 2022.06.29 |
---|---|
백준 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (0) | 2021.12.26 |
[ICPC] 백준 5419 - 북서풍 (0) | 2021.11.11 |
[COCI] 백준 2836 - 수상 택시 (0) | 2021.07.16 |