백준 : 18870번 좌표 압축 (c++)

백준 링크

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

코드 풀이

• N과 N만큼의 숫자를 담을 vecX 선언 및 정렬을 해줄 다른 벡터 vecNumb 선언
• 입력으로 주어진 N만큼 반복문 돌리며 vecX, vecNumb에 값 할당
• vecNumb정렬 및 중복 원소 제거
• N만큼 반복 돌리며 좌표 압축값 출력

쉽게 말해 예제와 같이 2, 4, -10, 4, -9의 숫자가 주어졌다고 가정을 하면

vecX, vecNumb의 초기 값은 2, 4, -10, 4, -9로 동일하게 되고 여기서 vecNumb값을 정렬하게 되면

vecX = 2, 4, -10, 4, -9

vecNumb = -10, -9, 2, 4, 4

가 되게 된다 이때 vecNumb의 중복값을 제거하게 되면

vecX = 2, 4, -10, 4, -9

vecNumb = -10, -9, 2, 4

가 된다

이 상태에서 lower_bound함수를 이용하여 vecX[i]의 값이 매칭되는 vecNumb의 인덱스값을 찾아내어 vecNumb.begin()를 빼주어 최종 정답을 도출해 낼 수 있다.

코드

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

using namespace std;

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

    int N;
    cin >> N;
    vector<int> vecNumb;
    vector<int> vecX;
    vecNumb.resize(N);
    vecX.resize(N);

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

    sort(vecNumb.begin(), vecNumb.end());
    // 중복원소 제거
    vecNumb.erase(unique(vecNumb.begin(), vecNumb.end()), vecNumb.end());

    for (int i = 0; i < N; ++i)
    {
        cout << lower_bound(vecNumb.begin(), vecNumb.end(), vecX[i]) - vecNumb.begin() << ' ';
    }

    return 0;
}