[C++] 2370번 시장 선거 포스터

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

---

 

25/03/18

 

 

이전에 해결했던 좋은 문제인데, 복습할 겸 다시 적어본다.

---

 

문제 접근 방식:

 

 

일단 이 문제에는 아주 간단하고 나이브한 솔루션이 존재한다. 그 전에 내가 먼저 해결했던 방법을 소개하고자 한다.

 

문제를 요약하자면 다음과 같다.

 

1. 포스터를 순서대로 붙임.

2. 즉, 포스터가 시작하는 지점 $l$과 끝나는 지점 $r$이 쿼리로 주어짐.

3. 쿼리가 다 끝난 뒤에 보이는 서로 다른 포스터의 개수를 구하는 것이 우리의 목적.

 

포스터가 위치할 수 있는 범위는 $1$부터 $100 \ 000 \ 000$ ($1$억)까지이다. 또한 쿼리의 개수는 최대 $10 \ 000$($1$만)까지이다.

 

가장 단순한 방법은, $1$억짜리 배열을 하나 만들고, 실제로 쿼리가 주어질 때마다 $l$부터 $r$까지 색칠(덮어 쓰기) 하며, 나중에 몇개가 보이는지 확인하는 것이다.

 

이 방법은 시간 복잡도 $\mathcal{O}(QN)$이 소모된다. (여기서 $N$은 포스터가 위치할 수 있는 최대 범위 좌표이다.)

 

당연히 $1$조의 시간 복잡도로 문제를 해결할 수는 없을 것이다.

 

여기서 생각할 수 있는 부분은, 포스터가 위치할 수 있는 최대범위의 좌표가 꽤나 크다는 점이다. 이에 비해 쿼리의 개수는 매우 적어($1$만개), 실제로 포스터가 시작하는 좌표 $l$과 포스터가 끝나는 좌표 $r$의 개수가 최대 $2$만개로 주어짐을 알 수 있다.

 

따라서 우리는 $1$억짜리 배열을 만들지 않아도 된다. 결국 포스터가 곂치는 것은 좌표의 대소관계에 의해서만 결정되기 때문에, 시작하는 좌표와 끝나는 좌표만 받은 다음에, 이를 1:1로 매칭시켜서 압축시키면 된다.

 

예를 들자면, 1 10과 2 11이 주어진다면, 실제로 들어오는 서로 다른 좌표의 개수는 4개가 되기 때문에, 1을 1에, 2를 2에, 10을 3에, 11을 4에 대응시키는 식으로 구성한다면 실제로 11까지의 좌표를 직접 만들지 않아도 범위가 많이 줄어든다.

 

이렇게 좌표 압축을 사용한다면 시간 복잡도 $\mathcal{O}(Q^{2})$이 소모된다.

 

사실 이 상태에서 풀어도 풀린다. 이게 첫번째 풀이 방법이다. $Q$가 $1$만이라, 나는 시간 내에 돌아가지 않을 것이라고 판단하여 다른 방법으로 풀고자 했다.

 

두번째 풀이 방법은 이 방법을 더욱 최적화 한 것이다.

 

첫번째 풀이 방법을 생각해보면, 그냥 순서대로 포스터를 덮는다. 그리고 나중에 보이는 거를 센다.

 

거꾸로 생각해보면, 가장 나중에 붙여진 포스터는 항상 보이게 된다는 특징이 있다. 이를 이용하여 가장 나중에 붙여진 포스터 먼저 붙여주도록 한다.

 

이후 다음 포스터는 이미 붙여진 포스터를 고려하여, 부분적으로 붙이기만 하면 된다!

 

예를 들자면, 1 10과 2 11 순서로 주어져있다면, 2 11 먼저 붙인 다음에, 1 10을 붙이는데, 실제로는 1만 붙이면 되므로 시간이 줄어든다. 

 

그러면 결국, 부분적으로 붙이기 위해서는 이미 붙여진 부분을 "빠르게" 넘길 필요가 있다. 하나하나 보면서 "음 이건 붙여져있군"하고 판단한다면, 이전과 똑같은 시간 복잡도를 가지게 될 것이다.

 

이미 붙여진 부분을 빠르게 넘기기 위해서는 분리 집합의 아이디어를 사용한다.

 

현재 위치에서, 현재 위치보다 같거나 오른쪽에 위치하면서 포스터가 붙여지지 않은 가장 왼쪽의 공간을 부모로 설정하도록 한다.

 

이후 순회할 때 find함수를 통해 실제로 붙여진 부분을 통채로 넘어갈 수 있으므로 이전보다 더 빠르게 순회할 수 있다.

 

붙이는 과정은 merge함수를 통해 구현할 수 있다.

 

좌표압축 이후 중간에 정렬이 사용되므로, 시간 복잡도는 $\mathcal{O}(Q \log Q + \alpha(Q) Q) = \mathcal{O}(Q \log Q)$의 시간 복잡도로 문제를 해결할 수 있다.

 

어떤 사람은 거꾸로 처리하는 아이디어는 그대로 유지한 채, 결국 개수만 세는 문제로 치환하여 "레이지 세그먼트 트리", 혹은 "이분 탐색"으로 문제를 해결하기도 했다.

 

각각의 방법으로도 해결하면 좋을 듯하다. 레이지 세그, 이분 탐색 모두 시간 복잡도는 동일하다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 2370번 시장 선거 포스터
// 오프라인쿼리, 좌표 압축, 집합과 맵, 분리집합
/*
접근 방법:
먼저 포스터의 좌표를 모두 받아주고, 가능한 포스터의 좌표의 범위를 압축해줍시다.
포스터의 개수는 10000개이므로 가능한 좌표의 최대 개수는 2만개 입니다.
이후 가장 나중에 붙여진 포스터부터 가장 먼저 붙여진 포스터 순으로 순회하며 다음과 같은 과정을 거칩니다. 

1. 나중에 붙여진 포스터는 적어도 먼저 붙여진 포스터와 우선순위가 동등하거나 항상 위에 붙어있습니다. 

2. 즉, 나중에 붙여진 포스터는 먼저 붙여진 포스터에 비해 더 높은 우선순위를 가집니다.

3. 그래서 나중에 붙여진 포스터를 먼저 주어진 대로 색칠합니다.

4. 이후 다음 포스터는, 나중에 붙여진 포스터 뒤에 붙여지므로 이를 고려하여 분리집합을 사용합시다.

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

int find(vector<int>& par, int node){
    if (par[node] != node){
        par[node] = find(par, par[node]);
    }
    return par[node];
}

void merge(vector<int>& par, int node1, int node2){
    int p1 = find(par, node1), p2 = find(par, node2);
    if (p1 != p2){
        if (p1 < p2){
            par[p1] = p2; 
        }
        else{
            par[p2] = p1;
        }
    }
    return;
}

int main(void){
    fastio;
    unordered_map<int, int> posToIdx;
    vector<pair<int, int>> query;
    int N; cin >> N;
    vector<int> number;
    int s, e;
    for (int i = 0; i < N; i++){
        cin >> s >> e;
        number.push_back(s);
        number.push_back(e+1);
        query.push_back({s, e+1});
    }
    // 정렬
    sort(number.begin(), number.end());
    // 좌표 압축
    int idx = 0;
    for (int num: number){
        if (posToIdx.find(num) == posToIdx.end()){
            posToIdx[num] = idx;
            idx++;
        }
    }
    vector<int> parent(idx, 0);
    for (int i = 0; i < idx; i++){
        parent[i] = i;
    }
    int ans = 0;
    for (int q = N-1; q >= 0; q--){
        bool ok = false;
        int l = posToIdx[query[q].first], r = posToIdx[query[q].second];
        while (find(parent, l) < r){
            int p = find(parent, l);
            if (p >= idx) break;
            merge(parent, p, p+1);
            ok = true;
        }
        if (ok) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}