BOJ 10165 버스 노선

처음 생각한 방법은 노선 길이가 가장 긴 구간부터 구간에 겹치는지 안겹치는지 확인하려고 하였다. 여기서 발생한 문제는 정류소의 갯수가 3 ~ 1,000,000,000개 이기 때문에 모든 정류소를 배열로 정의할 수 없다. 따라서 어떤 노선이 다른 노선에 포함되는지 안되는지 한번에 알수 있는 방법이 필요하다.

 

만약 모든 노선 a,b에서 a<b 이라면 특정 노선이 포함되는지 알수 있는 방법은 a를 내림차순, b를 오름차순으로 정렬한 후 정렬된 i번째 노선이 유효한지 확인하려면 "i보다 작은 노선 중 유효한 노선"(here이라고 하자)의 끝보다 현재 노선의 끝이 큰지만 확인하면 된다. 현재 노선 끝이 더 크다면 겹치지 않기 때문에 유효한 노선임을 알수 있다.

 

하지만 노선 a,b에서 a>b 라면 조금 복잡하다. 예를들어 [0~3]와 [9~4]는 위의 방법을 적용할 수 없다. 위의 방법을 적용한다면 겹치는 노선임에도 불구하고 겹치지 않는 유효한 노선이 되버린다. 이를 해결하기 위해 노선을 직선상으로 바꿔보자.

 

a>b 일때 a<b인 방법으로 변환하는 방법은 두가지 이다. [a-n~b], [a~b+n]으로 표현한면 직선상에 표현할 수 있다.

이제 a>b 인 모든 노선을 a<b 인 노선으로 변경하였기 때문에 첫번재 방법을 적용여 문제를 해결한다.

 

한편 a>b 일때 직선상으로 변환하면서 노선을 두개를 추가하였기 때문에 결과에는 중복된 값이 저장된다. 따라서 중복된 값을 제거해야한다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, m;
struct Bus
{
	int s, e, idx;
};

bool cmp(Bus x, Bus y)
{
	if(x.s != y.s)
	{
		return x.s < y.s;
	}
	return x.e > y.e;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	vector<Bus> v;

	cin >> n >> m;

	for(int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		int len = 0;
		if(a < b)//정노선
		{
			v.push_back({ a,b,i });
		}
		else
		{//역노선일경우 
			v.push_back({ a - n,b,i });
			v.push_back({ a,b + n,i });
		}
	}

	sort(v.begin(), v.end(),cmp);

	vector<int> result = { v.front().idx };//첫번째 노선은 반드시 유요하다
	int here = 0;
	for(int i = 1; i < v.size(); i++)
	{
		if(v[here].e < v[i].e)
		{
			result.push_back(v[i].idx);
			here = i;
		}
	}

	sort(result.begin(), result.end());

	result.erase(unique(result.begin(), result.end()), result.end());

	for(int i = 0; i < result.size(); i++)
	{
		cout << result[i] << " ";
	}
}