[백준] 좌표 압축

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

18870번: 좌표 압축

우선 문제부터 요약해보면,

주어진 좌표들 각각에 대해 총 좌표중 본인보다 작은 것들의 갯수를 출력해야 하는 문제입니다.

 

<Solution>

이 문제에서 생각 해야 하는 부분들은, 

1. 중복된 값이 등장하는 경우에는 하나로 카운팅 해야한다

2. 숫자들이 총 1,000,000개 등장이 가능하기에, 매 숫자마다 전체를 탐색하면 시간초과가 된다

 

이렇게 두가지입니다. 

 

그래서 이 두가지 점을 고려해서 문제 해결방법을 세워보면, 

1. 중복을 제거하기 위해 set을 사용 2. set은 순서가 없으므로 vector로 변형 3. 해당 vector를 크기 순서대로 sorting 4. 순열의 각각의 원소에 대해 vector의 Index를 이진탐색을 통해 찾음

이 과정을 실제로 구현하면 아래와 같습니다. 

 

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int originalIntArray[1000000+10];
int totalInt;

int main(){
    cin >> totalInt;

    for(int i = 0; i<totalInt; i++){
        cin >> originalIntArray[i];
    }

    // remove duplicate by set
    set<int> intSet(originalIntArray, originalIntArray+totalInt);
    // set to vector
    vector<int> intVector(intSet.begin(), intSet.end());

    // sort vector
    sort(intVector.begin(), intVector.end());

    for(int i = 0; i<totalInt; i++){
        cout << lower_bound(intVector.begin(), intVector.end(), originalIntArray[i]) - intVector.begin() <<' ';
    }
    cout << '\n';

    return 0;


}