[백준/C++] 2370번: 시장 선거 포스터(G4)

문제

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

2370번: 시장 선거 포스터

 

사용한 알고리즘

2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복

-> 좌표압축

 

풀이

포스터의 개수 n의 범위는 1 ≤ n ≤ 10,000 이고,
각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r의 범위는 1 ≤ l < r ≤ 100,000,000 이다.

벽의 칸이 1~10^8으로 큰 범위를 가지므로 
실제로 붙이는 것처럼 배열 마킹한 후 카운트하는 방법으로는 AC받을 수 없다.

포스터의 실제 길이가 중요한 게 아니라
어떠한 포스터가 보이는 구간이 '있는지'가 중요하다.
즉, 실제 간격이 중요하지 않고 상대적인 크기만 중요하다.

그리고 벽의 전체 칸 범위는 1~10^8인데
실제 나올 수 있는 서로 다른 좌표는 20000가지 뿐이다. (포스터 최대 개수 10^4 * 왼오2)
즉, 좌표가 나올 수 있는 범위는 매우 큰데
실제 등장하는 좌표 개수는 적다.

이련 경우, 좌표압축을 쓴다면 크기가 20000인 배열을 이용해서 문제를 해결할 수 있다.
각  포스터의 l, r 을 상대적인 순서로 대응시켜보자.

 

(1,4) (2,6) (8,10) (3,4) (7,10) 로 예시를 들어보자.

1. 위의 좌표쌍을 입력받는다.
2. 좌표에 등장한 숫자들을 list 벡터에 담고 중복원소는 제거해준다.
   list = [1, 2, 3, 4, 6, 7, 8, 10]
3. 입력들어온 순서대로 좌표(l, r)을 좌표압축(l', r')해서 배열에 체크해준다.
   해당숫자(l, r)을 리스트에서 lower_bound로 찾았을 때 그 인덱스가 (l', r') 이다.
   
4. 배열을 순회하며 서로다른 포스터의 개수를 세주면 된다.

 

 

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<pair<int,int>> point; //좌표 쌍 입력받음
vector<int> list; //좌표에 등장한 real 숫자 다 넣고 -> 정렬 & 중복 제거
int mat[20001]; //포스터를 붙일 벽 (포스터개수<10000, 각 포스터당 l,r좌표 가지므로 등장가능한 좌표 max 개수는 20000)
vector<int> ans; //마지막에 보이는 포스터 종류 다 넣고 -> 정렬 & 중복 제거 -> ans.size()가 정답

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

     cin>>n;

    for(int i=0; i<n; i++){
        int l,r; cin>>l>>r;
        point.push_back({l,r}); // 1. 좌표 쌍 입력받음 (좌표압축 이전)
        list.push_back(l); list.push_back(r); //좌표에 등장한 숫자 다 넣음
    }
    sort(list.begin(), list.end());
    list.erase(unique(list.begin(),list.end()), list.end()); // 2. 좌표에 등장한 숫자 중복 제거


    for(int i=0; i<n; i++){
        // 3. 입력들어온 순서대로 좌표압축한 l,r좌표를 구해
        // 즉, list에서의 인덱스
        int l=lower_bound(list.begin(),list.end(),point[i].first)-list.begin();
        int r=lower_bound(list.begin(),list.end(),point[i].second)-list.begin();
        for(int j=l; j<=r; j++) mat[j]=i+1; // 3. 포스터 붙이기 (원래0인거랑 구분하기위해 i+1을 넣어줌)
    }

    // 4.
    for(int i=0; i<20000; i++){
        if(mat[i]>0) ans.push_back(mat[i]); //보이는 포스터 종류 다 넣음
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(),ans.end()), ans.end()); //보이는 포스터종류 중복제거

    cout<<ans.size(); //마지막에 보이는 포스터 종류의 개수가 정답!
    return 0;
}