[G2] 백준 13334번 철로 C++ 우선순위 큐, 정렬, 스위핑

리뷰

 

우선순위 큐 문제는 풀어도 풀어도 어려운 것 같다 ㅠㅠ

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

 

전역 변수

• n, d, ans : 사람의 수 n, 철로의 길이 d, 구간에 포함되는 사람의 최대 수를 저장할 변수 ans
• nums : 집과 사무실의 좌표를 저장할 pair<int, int>타입 배열, 크기는 10만으로 초기화 한다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고 nums배열에 집과 사무실 위치를 입력 받아준다.
2. s보다 e가 크다면 두 수를 바꿔주고, 도착 시간을 기준으로 오름차순 정렬을 할 것이기 때문에 e, s순으로 저장한다.
3. sort메서드를 통해 nums배열을 0부터 n - 1인덱스를 오름차순으로 정렬해 준다.
4. 정수형 타입의 우선순위 큐 pq를 초기화 해주고 오름차순으로 우선 정렬한다.
5. d값을 입력 받고 nums배열을 순회하는 반복문을 만들어 준다.
6. 만약 도착 지점 - 시작 지점이 d보다 작거나 크면 pq에 시작지점을 추가해 준다.
7. pq에 도착지점 - 철로의 길이보다 작은 시작지점들은 모두 pop해준다.
8. pq에 남은 정수들의 개수를 ans를 통해 최대값을 갱신해 준다.
9. 모든 작업이 완료된 후에 ans에 저장된 값을 출력해 준다.

 

참고 사항

오름차순이 아닌 도착 시간을 기준으로 오름차순 정렬을 해주어야 문제를 정확히 풀 수 있다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<algorithm>
#define pii pair<int, int>

using namespace std;

int n, d, ans;
pii nums[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int s, e; cin >> s >> e;
		if (s > e) swap(s, e);
		nums[i] = { e, s };
	}

	sort(nums, nums + n);
	priority_queue<int, vector<int>, greater<int>> pq;

	cin >> d;
	for (int i = 0; i < n; i++) {
		pii cur = nums[i];
		int s = cur.second, e = cur.first;

		if (e - s <= d) pq.push(s);
		else continue;

		while (!pq.empty() && pq.top() < e - d) pq.pop();

		ans = max(ans, (int)pq.size());
	}
	cout << ans;
}