[백준 C++] 13334번: 철로

1. 문제

https://www.acmicpc.net/problem/13334

 

2. 알고리즘 분류

• 자료 구조
• 정렬
• 스위핑
• 우선순위 큐

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, d, ret;
vector<pair<int, int>> pos;
priority_queue<int, vector<int>, greater<int>> pq;

bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
}

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

	// N : 사람의 수
	cin >> N;

	// 집과 사무실 거리 입력
	for (int i = 0; i < N; i++) {
		int h, o;
		cin >> h >> o;
		if (h > o) swap(h, o);
		pos.push_back({ h, o });
	}

	// d : 철로의 길이
	cin >> d;

	// end 거리 기준으로 오름차순 정렬
	sort(pos.begin(), pos.end(), cmp);

	// 각 사람마다 탐색
	for (int i = 0; i < N; i++) {
		int start = pos[i].first;
		int end = pos[i].second;

		// start ~ end 거리가 d를 넘어간 경우, skip
		if (end - start > d) continue;

		// 현재 start 거리 priorty_queue에 삽입
		pq.push(start);

		// priority_queue 탐색하면서, 현재 end 거리 기준으로 d 거리보다 긴 경우 제거
		while (!pq.empty()) {
			if (end - pq.top() <= d) break;
			pq.pop();
		}

		// 최대값 갱신
		ret = max(ret, (int)pq.size());
	}

	// 정답 출력
	cout << ret;

	return 0;
}

 

4. 유용한 알고리즘

1) 스위핑 알고리즘

1. 정의
 - 특정 기준에 따라 정렬한 후 순서대로 처리하는 알고리즘