백준 10165 버스 노선

https://www.acmicpc.net/status?user_id=museum114&problem_id=10165&from_mine=1

채점 현황

이런 문제는 경우의 수를 잘 쪼개는 게 중요한 것 같다.

 

이 문제를 어렵게 만드는 요인은 바로 '원형'이라는 점이다. 우리가 보기에는 원형이든 선형이든 상관없지만

 

컴퓨터에게 이 문제는 꽤 중요하다. 인덱스가 달라지기 때문이다. 

 

그래서 0(중심점)을 넘어서는 버스 노선은 특별한 연산을 거친 후 vector에 넣었다. 자세한 건 코드로 확인하시라~

 

/* 버스 노선 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

#define ll long long int
#define pp pair<ll,ll>

using namespace std;

ll N, M; // 숫자가 좀 크다 싶으면 long long int를 default로 사용하는게 맘편하다. 

bool is_visit[500000 + 1]; // 버스 노선 확인용(어떤 버스 노선이 살아남는가!)

vector<pair<int, pp> > bus; // int는 버스 노선 번호, pp는 <시작점, 끝점>이다. 

void input();
void solve();
inline bool comp(pair<int, pp> & a, pair<int, pp> & b) {
// 끝점이 같으면 시작점이 작은 순서대로 정렬한다. 
	if (a.second.second == b.second.second) {
		return a.second.first < b.second.first;
	}
    // 끝점이 다르면 끝점이 작은 순서대로 정렬한다. 
	return a.second.second < b.second.second;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input();
	solve();
	return 0;
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		ll a, b; cin >> a >> b;
		if (a > b) {
        
        // 끝점이 중점을 넘어가는 경우 시작점의 값이 끝점의 값보다 커진다.
        // 한바퀴를 도는 버스노선은 없다고 했으니 이정도로만 처리해도 된다.
        
			bus.push_back(make_pair(i, make_pair(a - N, b)));
			bus.push_back(make_pair(i, make_pair(a, b + N)));
		}
		else 
			bus.push_back(make_pair(i, make_pair(a, b)));
	}
}

void solve() {
	/* 끝 지점 기준으로 sort */
	sort(bus.begin(), bus.end(), comp);

	/* first point가 작으면 무조건 현재 것이 그것에 포함됨*/
	/* first point가 크더라도 second point가 같으면 포함됨 */
	/* second point가 크면 무조건 포함 안됨 */
	
	stack<pair<int, pp>> s;
	s.push(bus[0]);

	for (int i = 1; i < bus.size(); i++) {
		// 두 버스라인의 도착점이 같음
		if (s.top().second.second == bus[i].second.second) {
			is_visit[bus[i].first] = true;
		}
		// 버스라인의 도착점이 현재 도착점보다 뒤임.
		else {
			// 새로운 버스라인의 시작점이 현재 시작점보다 더 앞이면 현재 라인은 새로운 버스라인에 포함됨
			
			while (!s.empty() && s.top().second.first >= bus[i].second.first) {
				is_visit[s.top().first] = true;
				s.pop();
			}
			s.push(bus[i]);
		}
	}
	
	for (int i = 0; i < M; i++) {
		if (is_visit[i] == false) {
			cout <<i  + 1 << " ";
		}
	}
}