백준 18870 좌표압축

이번에 풀어본 문제는 좌표 압축이라는 문제입니다.
문제링크: https://www.acmicpc.net/problem/18870
난이도는 실버 2에 해당하는 문제입니다.
처음에 어떻게 접근할까 고민하던중, 브루트 포스로 풀수 있나 먼저 생각해보았습니다.
브루트 포스로 풀 경우, 생각한 방법은 처음 받은 정렬을 vector<int,int>로 선언해 앞쪽에는 index값을 그 뒤에는 좌표값을 받아, value값을 기준으로 정렬한 후 이중 for문으로 기준 좌표값보다 작은값이 있다면 +1더해주고, 겹친다면 continue로 넘어가는 방향으로 구현하려고 했지만,
해당 문제의 시간제한은 2초인데 들어올 수 있는 좌표값은 최대 1,000,000이므로, O(N^2)의 시간복잡도를 갖는 브루트 포스로 풀 경우, 시간초과가 발생하게 됩니다.

💡 그래서 생각한 방법은 vector을 활용해 value값을 기준으로 정렬하는 것은 동일하지만, pivot이라는 변수값 그리고 cnt라는 변수값을 두고 pivot값과 같지 않을 경우, pivot값을 변경해주고 ,cnt변수값을 증가시킨 후, 좌표를 압축한 결과를 저장하는 res라는 배열에 cnt값을 넣습니다.
한번의 for문을 통해 구현하며, 이미 정렬된 벡터이기 때문에 pivot값과 같지 않다면 큰 경우밖에 존재하지 않습니다.
이렇게 구현한다면 시간복잡도는 O(N) 를 만족해 시간초과가 발생하지 않습니다.

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

using namespace std;

//구조체 선언
struct ve{
    int index,value;
    ve(int a,int b){
        index=a;
        value=b;
    }
    //좌표값 기준으로 오름차 정렬
    bool operator <(const ve &b)const{
  
        return value<b.value;
    }
    
    
};


int main(){
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    
    int n;
    cin>>n;
    vector<ve>v;
    
    int a;
    for(int i=0;i<n;i++){
        cin>>a;
        v.push_back(ve(i,a));
    }
    
    sort(v.begin(), v.end());
    //기준값 초기 설정
    int pivot=v[0].value;
    int cnt=0;
    vector<int>res(n);
    for(int i=1;i<n;i++){
        //같은 값을 갖을 경우 cnt는 동일
        if(pivot==v[i].value){
            res[v[i].index]=cnt;
        }
        else{
            cnt++;
            res[v[i].index]=cnt;
            pivot=v[i].value;
        }
    }
    
    for(int i=0;i<n;i++){
        cout<<res[i]<<" ";
    }
    
    cout<<"\n";
    
    
    return 0;
}

주석을 참고하면 더욱 이해하기 쉬울 거 같습니다!
즐거운 코딩하세요 😊
읽어주셔서 감사합니다