(C++) - 백준(BOJ) 1689번 : 겹치는 선분

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

1689번: 겹치는 선분

priority_queue를 이용한 sweeping 문제였습니다.

 

 

 

📕 풀이방법

📔 입력 및 초기화

 1. 선분 시작좌표, 선분 끝 좌표를 pair로 한 vector형 자료구조 v를 선언하고 n만큼 입력받습니다.

 

 2. v를 오름차순으로 정렬해줍니다. 기준은 first먼저 그 다음 second로 정렬됩니다.

 

 3. min heap인 priority_queue 변수 pq를 선언해줍니다.

 

 4. 답을 출력할 ans는 1부터 시작합니다. 이는 가장 처음에 기준값이 될 0번째 선분을 먼저 pq에 넣기 때문입니다. 또한 선분은 최소 1개부터 겹치므로 ans의 최솟값 또한 1입니다. 

📔 풀이과정

 1. 가장 시작좌표가 작은 첫 번째 선분의 끝좌표를 pq에 push합니다.

 2. 이후 1 ~ n-1번째 선분까지 loop를 돌며 다음을 수행합니다.

 

  2-1. 새로운 선분의 첫 번째 좌표 이하인 동안 pq의 원소를 pop해줍니다. 이는 기존에 겹치는 선분에 대한 비교를 마쳤기 때문입니다. 현재 선분의 시작 좌표는 이전 선분의 끝 좌표와 겹쳤을 때도 답이 아니기 때문에 '이하'이어야 합니다.

 

  2-2. 새로운 선분의 끝 좌표를 pq에 push해줍니다. 이는 새로운 기준이 되며 다음 새로운 선분의 첫 번째 좌표가 그 기준을 통과하지 못할 때까지 계속 갱신되며 pq의 크기가 늘어나게 됩니다.

 

  2-3. 남아있는 pq의 크기와 기존 ans와의 최댓값을 비교해 더 큰 값을 ans에 저장합니다.

 

📔 정답출력

 ans를 출력합니다. 

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
using pii = pair<int,int>;
int n, ans = 1;
vector <pii> v;
int main(){
    fastio;
    cin >> n;
    v.resize(n);
    for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(),v.end());

    priority_queue <int,vector<int>,greater<int>> pq;
    pq.push(v[0].second);
    for(int i = 1; i < n; i++){
        int startPoint = v[i].first;
        int endPoint = v[i].second;

        while(pq.size() && pq.top() <= startPoint) pq.pop();
        pq.push(endPoint);
        ans = max(ans,(int)pq.size());
    }
    cout << ans << '\n';
}