BOJ - 18870 좌표 압축

여러 수 중 자신보다 작은 것들의 갯수를 구하는 문제이다.

단, 작은 것들이 중복되는 경우는 하나로 취급해야 한다.

문제해결 전략

주어진 수들을 정렬한 후 갯수를 세 나가는데, 중복되면 카운트 안하는 방식으로 계산하면 된다.

처음에는 중복을 체크하기 위해 map 자료구조를 이용하였다. (주석부분)

현재 확인하고자 하는 수가 map에 존재하지 않는다면 카운팅 하고 map에 추가해 준다.

위 과정을 마지막 수까지 반복하면 된다.

두번째 방법은 다른 분들의 코드를 참고하였다.

algorithm의 unique()를 사용하여 중복된 것들을 뒤로 뺀후 vector의 erase()를 이용하여 뒤의 것들을 제거해 준다. 이 과정에서 중복된 것들을 벡터에서 제거해 준다.

그 다음으로 lower_bound()를 이용하여 key의 위치를 찾아 출력해 주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> v, w;
    for(int i=0;i<n;i++){
        int m;
        cin >> m;
        v.push_back(m);
        w.push_back(m);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i=0;i<w.size();i++){
        cout << lower_bound(v.begin(), v.end(), w[i]) - v.begin() << " ";
    }
    cout << "\n";

    return 0;
}


//int main() {
//    int n;
//    cin >> n;
//    map<int,int> ma;
//    vector<int> v;
//    vector<int> w;
//    for(int i=0;i<n;i++){
//        int m;
//        cin >> m;
//        v.push_back(m);
//        w.push_back(m);
//    }
//
//    sort(v.begin(), v.end());
//
//    int cnt = 0;
//    for(int i=0;i<v.size();i++){
//        if(ma.find(v[i]) == ma.end()){
//            ma.insert(make_pair(v[i], cnt));
//            cnt++;
//        }
//    }
//
//    for(int i=0;i<w.size();i++){
//        cout << ma[w[i]] << " ";
//    }
//    cout << "\n";
//
//    return 0;
//}

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