[C++] 백준 18870 : 좌표 압축

메모리도 고려하고 푸는 방식도 전부 생각해냈지만 아쉽게 시간 복잡도 때문에 좀 헤멘 문제.
STL 라이브러리 사용도 연습해 볼 수 있었다.

O(N^2)는 불가능하고 O(N logN)의 시간 복잡도에 맞춰야한다.

lower_bound : 이진탐색기반. 해당하는 값보다 크거나 같은값이 제일 처음 등장하는 곳 위치를 리턴. (정렬 전제)
찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함

반환형이 iterator 이므로 인덱스를 알고싶다면 배열 첫번째 주소를 가리키는 배열의 이름을 빼면 됨

lower_bound를 사용하여 for문 2개를 돌리지않고 이진 탐색 O(log N) 시간 복잡도를 사용하여 허용한다.

#include <iostream>
#include <vector>
#include <algorithm> // sort, unique
using namespace std;

int N, x;
vector<int> v;
vector<int> sortV;
int main(int argc, char **argv){
    scanf("%d", &N);

    for(int i=0; i<N; i++){
        scanf("%d", &x);
        v.push_back(x); // 좌표 입력받아 저장
        sortV.push_back(x); // 정렬할 벡터
    }

    sort(sortV.begin(), sortV.end()); // 벡터 정렬 -> 선 정렬해야 중복 삭제 가능
    sortV.erase(unique(sortV.begin(), sortV.end()), sortV.end()); // 중복되는 원소 삭제
    

    for(int i=0; i<v.size(); i++){
        printf("%ld ", lower_bound(sortV.begin(), sortV.end(), v[i]) - sortV.begin());
        // 순서대로 정렬된 벡터의 인덱스를 구하여 출력
    }

    return 0;
}

시간 초과가 난 코드.
for문 2개를 사용하여 O(N^2)의 시간복잡도를 가진다.
문제의 시간 복잡도는 sort 함수의 O(N logN) 의 복잡도까지만 허용한다.

#include <iostream>
#include <vector>
#include <algorithm> // sort, unique
using namespace std;

int N, x;
vector<int> v;
vector<int> sortV;
int main(int argc, char **argv){
    scanf("%d", &N);

    for(int i=0; i<N; i++){
        scanf("%d", &x);
        v.push_back(x); // 좌표 입력받아 저장
        sortV.push_back(x); // 정렬할 벡터
    }

    sort(sortV.begin(), sortV.end()); // 벡터 정렬 -> 선 정렬해야 중복 삭제 가능
    sortV.erase(unique(sortV.begin(), sortV.end()), sortV.end()); // 중복되는 원소 삭제
    

    for(int i=0; i<v.size(); i++){
        for(int j=0; j<sortV.size(); j++){
            if(v[i] == sortV[j]){
                printf("%d ", j);
                break;
            }
        }
    }

    return 0;
}