백준 18870 좌표 압축 C++

- 문제

문제 보러가기

정렬, 값 / 좌표 압축으로 알고리즘 분류가 되어있는 문제입니다. 문제를 다 풀고 다른 분들의 풀이를 보았는데 보통 vector의 lower_bound, unique 함수 두 가지를 이용한 풀이가 많았습니다. 저는 두 함수를 몰랐기 때문에 이상한 방법으로 풀었지만....내가 푼 방법을 정리하고, 위 함수들을 공부해보겠습니다!

- 문제 풀이

• vector<pair<int, int>> 구조를 두 번 사용하는데, 처음 vector의 pair는 input, index이고 두번 째 vector의 pair는 index와 zip(압축된 값)이다.
• 첫 번째 벡터에 주어진 수와 index를 저장한 후 정렬한다.
• 반복문을 돌면서 두 번째 벡터에 index와 압축된 값을 저장한다.
• 두 번째 벡터를 index 기준으로 정렬하고 압축된 값(정답)을 출력한다.
  * 정렬 -> 압축 -> 정렬을 통해 압축을 위해 원하는 형태로 정렬한 vector를 다시 정렬해준다고 보면 쉽다.

- 코드

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

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

    int N, num;
    vector<pair<int, int>> vec;
    vector<pair<int, int>> result;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> num;
        vec.push_back(pair<int, int>(num, i));
    }

    sort(vec.begin(), vec.end());

    result.push_back(pair<int, int> (vec[0].second, 0));

    int zip = 0;
    for(int i = 1; i < N; i++){
        if(vec[i-1].first != vec[i].first) zip++;
        result.push_back(pair<int, int>(vec[i].second, zip));
    }

    sort(result.begin(), result.end());

    for(auto r : result){
        cout << r.second << " ";
    }

    return 0;
}