이 문제를 처음 접했을 때는 크기 순으로 정렬시킨 배열을 하나 더 생성하여 그 배열의 인덱스 값을 결과 배열에 넣고, 결과 배열에서 같은 값을 가진 수만큼 빼면 답을 구할 수 있을 거라고 생각했다.

• x배열과 x2배열을 만들고 x배열의 값을 x2배열에 복사한다.
• x2배열을 순서대로 정렬시킨다.
• x배열과 x2배열을 이중 포문으로 비교하여 값이 같을 때 result배열에 인덱스 값을 넣는다.
• result 배열에 같은 값이 들어가는 수를 cnt에 저장하여 그만큼 빼준다.

이 방식은 배열의 길이가 길고 들어가는 수의 가지수가 적을 때 원하는 결과를 도출할 수 없었다.
구글링을 통해 알게 된 방식은 algorithm헤더의 unique를 사용하는 방식이다.

• x벡터와 x2벡터에 같은 값을 넣는다.
• x2벡터를 순서대로 정렬시킨다.
• unique함수로 x2벡터의 중복값을 지워준다.
• lower_bound함수를 통해 x벡터의 i번째 원소가 x2벡터의 몇번째에 위치하는지 확인한다.
• result배열에 lower_bound반환값-시작 주소값을 넣어준다.

Code

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 1000001
using namespace std;

int n;
vector<int> x;
vector<int> x2;
int cnt=0;
int result[MAX];

void Input(){
    int a;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a;
        x.push_back(a);
        x2.push_back(a);
    }
}

void Solution(){
    sort(x2.begin(), x2.end());
    x2.erase(unique(x2.begin(), x2.end()), x2.end());
    for(int i=0; i<n; i++){
        result[i]=lower_bound(x2.begin(), x2.end(), x[i])-x2.begin();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    for(int i=0; i<n; i++){
        cout<<result[i]<<" ";
    }
    return 0;
}