18870번: 좌표 압축

18870번:  좌표 압축

사용 언어: C++

 

풀이

실제로 값들을 비교해서 푸는게 아니라, 값들을 받아서 정렬 후 (중복값도 빼주면서), 정렬하지 않은 배열의 원소가 정렬된 배열의 몇 번째 인덱스인지 알아내면 그 값이 그 원소가 다른 몇 개의 원소보다 큰지 개수다.

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    int A[N];
    for(int i=0; i<N; i++)
    {
        cin >> A[i];
    }
    vector<int> C;

    for(int i=0; i<N; i++)
    {
        C.push_back(A[i]);
    }

    sort(C.begin(), C.end());
    // "unique" rearranges vector and collapses duplicate element
    // "erase" actually removes the duplicates and adjust vector size
    C.erase(unique(C.begin(), C.end()), C.end());

    for(int i=0; i<N; i++)
    {
        // Searches for A[i] and finds the index in C, which is the number of comparisons
        A[i] = lower_bound(C.begin(), C.end(), A[i]) - C.begin();
    }

    for(int i=0; i<N; i++)
    {
        cout << A[i] << " ";
    }
}