[백준] 1689번 겹치는 선분 (C++)

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

 

 

이 문제는 N개의 선분이 주어졌을때 선분중에 최대한 겹치는 선분의 개수를 구하는 문제이다.

 

선분은 시작점과 끝점이 주어진다 이때 점에서 점으로 겹치는 것은 세지 않는다.

 

문제를 풀기전에 테스트 케이스 1번이 어떻게 답이 저렇게 나오는지 그림을 그려보았는데 어떤 규칙성을 발견했다.

 

 

N개의 점을 시작점을 기준으로 정렬을 한 이후 그려보았을때 선분을 담는 그릇이 존재해야된다고 생각하였다 이때 어차피 시작점을 기준으로 선분을 차례로 보기 때문에 끝점중에서 가장 작은것과 비교하면서 넣어주고 빼주면 되지 않을까 생각하고 바로 구현하였다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
vector<pair<ll, ll>> v;
priority_queue<ll, vector<ll>, greater<ll>> pq;

void solve() {
    int answer = 1;
    sort(v.begin(), v.end());

    pq.push(v[0].second);

    for(int i = 1; i < N; i++) {
        if(!pq.empty() && pq.top() <= v[i].first) pq.pop();
        pq.push(v[i].second);
        answer = max(answer, (int)pq.size());
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

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

    input();
    solve();
}

 

코드를 하나씩 살펴보자

 

void solve() {
    int answer = 1;
    sort(v.begin(), v.end());

    pq.push(v[0].second);

    for(int i = 1; i < N; i++) {
        if(!pq.empty() && pq.top() <= v[i].first) pq.pop();
        pq.push(v[i].second);
        answer = max(answer, (int)pq.size());
    }

    cout << answer;
}

가장 핵심인 함수다 우선순위 큐를 최소힙으로 설정하고 배열을 정렬한 이후 첫번째 선분의 끝점을 넣는다

이후 하나씩 살펴보며 최소힙중 가장 짧은 끝점과 현재 넣을 시작점을 비교한다. 끝점이 만약 짧은 경우

기존에 있는 짧은 끝점은 포함이 안되기 때문에 현재 최소힙의 끝점이 현재 넣어야하는 시작점보다 커질때까지 pop을 한다.

 

이후 현재 힙의 크기가 겹치는 선분의 크기이므로 갱신한다.

 

이것을 더욱 간단하게 푸는 방법도 찾아보았다.

 

스위핑이라는 알고리즘을 사용하는데

 

스위핑이란 어떤 선이나 공간을 한쪽에서부터 싹 쓸어버린다는 의미이며

스위핑 기법이란 한번만 전체 공간을 스캔하면서 마주치는 요소들에 뭔가를 해주면 정답이 구해지는 형태이다.

 

선분은 시작점과 끝점이 존재한다. 이때 미리 배열을 선언하고 시작점은 +1, 끝점은 -1로 설정하여 정렬을 한다.

 

이후 배열을 순회할때 +1, -1을 계속 더해주며 최댓값을 갱신한다.

 

이것이 가능한 이유는 선분은 시작점과 끝점이 존재하며 왼쪽의 축을 잡는경우 선분은 오른쪽으로 뻗어나가고 끝점이 존재하기 때문에

선분과 선분을 겹치는 것을 알기 위해선 시작점, 도착점이 겹치는 것을 정렬하여 더하고 빼면 되기 때문이다.