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

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

이번 문제는 좌표압축이 뭔지 배우는것부터 시작했다.

 

좌표압축의 개념은 아래 포스팅에서 정리했고,

좌표 압축 알고리즘 이란?

이걸 가지고 문제를 바로 풀기에는 개념이 너무 어색해서, 먼저 다른사람들의 풀이를 보고 이를 분석하여 푸는 방식으로 진행하였다.

 

여기에서 새롭게 배운 개념중 하나는 lower_bound함수였는데, 이 함수는 <algorithm> 헤더 안에 포함되어있으며, 먼저 sort 함수를 통해 정렬되어있어야한다는 전제가 필요하다. 

lower_bound(first, end, x) 는 first ~ end에서  x이상의 값이 나오는 첫번째 원소의 위치를,

upper_bound(first, end, x) 는 first ~ end에서  x초과의 값이 나오는 첫번째 원소의 위치를 반환한다.

 

또한 unique, resize함수를 사용해서 정렬한 배열의 중복을 제거하는 방식또한 배웠다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> v, idx;

int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a;
        scanf("%d", &a);
        v.push_back(a);
        idx.push_back(a);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());

    for (int a : idx)
    {
        int pos = lower_bound(v.begin(), v.end(), a) - v.begin();
        printf("%d ", pos);
    }
}