[G4] 백준 1689번 겹치는 선분 C++ 그리디 알고리즘, 정렬, 우선순위 큐

리뷰

 

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

1차원 좌표계 위에 선분이 최대로 겹쳐있는 부분의 겹친 선분의 개수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 선분의 개수를 저장할 변수
• a : 선분의 시작점과 끝 점을 저장할 배열

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 선분의 시작과 끝점의 좌표를 입력 받아 a배열을 초기화한다.
2. sort함수를 통해 a배열을 오름차순으로 정렬해준다.
3. 변수 ans를 0으로 초기화 하고, 정수형 오름차순 우선순위 큐 pq를 초기화한다.
4. n개의 선분을 순회하며 현재 선분의 시작 점보다 끝점의 좌표가 작거나 같은 선분을 pq에서 모두 빼내어준다.
5. pq에 현재 선분의 끝 점을 push한다.
6. ans를 현재 pq의 size()와 비교하여 더 큰 값으로 ans에 저장한다.
7. ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 선분의 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.
2. 선분의 좌표는 절댓값이 10억보다 작거나 같은 정수이다, int범위로 해결이 가능하다.

 

정답 코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;

const int N = 1e6;
int n;
pii a[N];

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int s, t; cin >> s >> t;
		a[i] = { s, t };
	}
	sort(a, a + n);

	int ans = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < n; ++i) {
		pii d = a[i];

		while (!pq.empty() && pq.top() <= d.first) pq.pop();
		pq.push(d.second);

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