[백준 13334] 철로 (C++)

문제 링크: https://www.acmicpc.net/problem/13334

13334번: 철로

1. 주의할 점

- N^2만큼 확인하는 코드를 작성하지 않도록 한다. 우선순위큐나 Set을 사용한다(물론 중복값이 있을 수 있으므로 멀티셋 사용)

- 각각에 대한 정렬방식을 미리 정해둔다

 

2. 구현

- 입력받는 수를 우선순위큐 PQ에 저장하며, 도착지점의 오름차순이 1순위이며 시작지점의 오름차순이 2순위다(도착지점이 같다면)

- 우선순위큐에서 1개씩 빼며, 시작지점과 도착지점의 차이가 Limit이하면 또 다른 우선순위큐 Q에 시작지점만 넣는다(어차피 도착지점이 오름차순으로 이미 정렬되어 있기 때문에). 이때, Q도 시작지점을 오름차순으로 정렬되도록 한다. 

(-1 2), (-2 3), (3 4), limit: 5 같은것을 처리해야 하기 때문이다.

- Q의 Top과 현재 도착지점의 차이가 Limit 이하일때까지 Q에서 Pop하고, Q의 Top과 도착지점의 차이가 Limit 이하라면 Result와 Q의 사이즈를 비교하여 큰 값을 Result에 할당한다

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
	long long s, e;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.e == b.e)
			return a.s > b.s;
		return a.e > b.e;
	}
};
info tmp;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	long long s, e, limit;
	int num, result = 0;
	cin >> num;
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < num; i++) {
		cin >> s >> e;
		//오른쪽 부분이 먼저 입력으로 들어올 수 있다
		tmp.s = min(s, e);
		tmp.e = max(s, e);
		pq.push(tmp);
	}
	cin >> limit;
	priority_queue<long long,vector<long long>, greater<long long>> q;
	while (!pq.empty()) {
		int cs = pq.top().s;
		int ce = pq.top().e;
		pq.pop();
		if (ce - cs <= limit)		//철로의 길이 사이에 위치한다면 우선순위 큐에 시작점 삽입
			q.push(cs);
		while (!q.empty()) {
			if (ce - q.top() <= limit)
				break;
			else
				q.pop();
		}
		int len = q.size();
		result = max(result, len);
	}
	cout << result;
	system("pause");
	return 0;
}