[Baekjoon/C++] 18870번 좌표 압축

문제 설명

입출력 예

코드 구현 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N=0;
    cin >> N;

    vector<int> vec(N);
    vector<int> vec2(N);

    vector<pair<int, int>> pvec;
    vector<pair<int, int>> pvec2;

    for(int i=0; i<N; i++){
        cin >> vec[i];
        vec2[i]=vec[i];
    }

    //중복제거
    sort(vec2.begin(), vec2.end()); //unique함수는 연속된 중복요소만 제거하기 때문에 sorting 필요
    vec2.erase(unique(vec2.begin(), vec2.end()), vec2.end());

    int count=0;
    for(int i=0; i<vec2.size(); i++){
        for(int j=0; j<vec2.size(); j++){
            if(vec2[i]>vec2[j]){
                count++;
            }
        }
        pvec2.push_back({vec2[i], count});
        count=0;
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<pvec2.size(); j++){
            if(vec[i]==pvec2[j].first){
                pvec.push_back({pvec2[j].first, pvec2[j].second});
            }
        }
    }

    for(auto p: pvec){
        cout << p.second << " ";
    }

    return 0;
}

입출력 예제는 다 맞았는데 시간초과가 떴다.

코드 구현 2

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N=0;
    cin >> N;

    vector<int> vec(N);
    vector<int> vec2(N);

    for(int i=0; i<N; i++){
        cin >> vec[i];
        vec2[i]=vec[i];
    }

    //중복제거
    sort(vec2.begin(), vec2.end()); //unique함수는 연속된 중복요소만 제거하기 때문에 sorting 필요
    vec2.erase(unique(vec2.begin(), vec2.end()), vec2.end());

    unordered_map<int, int> vcount; //키가 정렬되지 않아야 하므로 unordered_map 사용

    for(int i=0; i<N; i++){
        //vec[i]의 위치에서 vec.begin() 위치를 빼면 vec[i]앞에 있는 원소들의 총 개수가 된다.
        int count = lower_bound(vec2.begin(), vec2.end(), vec[i]) - vec2.begin();
        vcount[vec[i]]=count;
    }

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

    return 0;
}

이중for문을 삭제하고 unordered_map과 lower_bound를 추가해서 다시 풀어 봤더니 시간초과가 해결되었다.

공부한 내용

unordered_map

[C++] map vs unordered_map

lower_bound

• 특정값보다 작은 값을 개수를 구하는데 유용
• lower_bound는 특정값 이상인 값이 처음 등장하는 위치를 알려주기 때문

사용예시

vec=[1, 2, 3, 4, 5]
lower_bound(vec.begin(), vec.end(), 3); //vec[2]을 반환
lower_bound(vec.begin(), vec.end(), 3)-vec.begin(); //3의위치 - 시작위치 = 3보다 작은 원소 개수

vec가 이미 정렬되어 있으니 3 왼쪽에 있는 값들은 모두 3보다 작은 값이 된다.

---

출처: 백준, https://www.acmicpc.net/problem/18870