[18870] 좌표 압축

📝 문제

18870번 : 좌표 압축

💡 생각

각 좌표들 중 가장 작은 값은 0으로 치환하고, 커질수록 1씩 증가하는 값으로 치환하는 문제이다.
입력받는 값들의 순서를 매겨야 하므로 정렬해서 값을 할당해야 하는데 이 상대좌표들을 다시 입력받은 순서대로 출력하는 과정을 고민하였다.

내가 구현한 방법은 pair 배열을 이용해서 원 좌표와 상대좌표 값을 pair에 담아, 입력 시 저장된 순서대로 출력하는 방법이다.

포인터 개념이 잘 안잡혀 있어서 처음에 그냥 값만 넘겨준 후 정렬을 하니 처음에 만든 자료형에 값이 담겨 있지 않았다.
벡터안에서 연산을 처리해도 원래 만든 자료형에 영향을 미치게끔 해야하므로 주소값을 넘겨주어야 한다.

1. 원 좌표(double)와 상대좌표(int)를 하나의 객체로 취급하기 위해, pair 객체(편의상 좌표쌍으로 명명)을 담을 배열 선언

2. 원 좌표를 입력받은 숫자, 상대좌표를 0으로 하여 좌표쌍을 생성하여 배열에 삽입

3. 좌표쌍을 담는 배열의 주소값을 벡터에 push

4. 좌표쌍의 원 좌표를 기준으로 오름차순으로 정렬

5. 정렬된 순서를 통해 상대좌표 값 수정

6. 좌표쌍 배열 순서대로(입력받은 순서) 상대좌표 값 출력

💻 코드

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

using namespace std;

bool comp(pair<double, int>* p1, pair<double, int>* p2) {	// 원 좌표 값을 기준으로 오름차순으로 정렬하기 위한 비교함수
    if (p1->first < p2->first)
        return true;
    else
        return false;
}

int main() {

    int N, n;
    pair<double, int> p[1000000];	// 1 ≤ N ≤ 1,000,000
    vector<pair<double, int>*> v;	// sort 후 상대좌표를 할당하기 위한 벡터

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> n;
        p[i] = make_pair(n, 0);	// 입력받을 때 상대좌표 자리에는 0을 넣어준다.
        v.push_back(&p[i]);
    }

    sort(v.begin(), v.end(), comp);

    for (int i = 1; i < v.size(); i++) {
        if (v[i - 1]->first == v[i]->first)
            v[i]->second = v[i - 1]->second;	// 좌표값이 같다면 상대좌표에 이전의 상대좌표와 같은 값 할당
        else
            v[i]->second = v[i - 1]->second + 1;	// 좌표값이 다르다면 상대좌표에 이전의 상대좌표+1 값 할당
    }

    for (int i = 0; i < N; i++)
        cout << p[i].second << ' ';
}

다른 분들의 풀이를 보니, 대부분
1. 좌표 값을 두개의 벡터에 입력받음
2. 하나의 벡터를 정렬 후 중복제거
3. 정렬되지 않은 벡터에서 정렬된 값을 찾음(lower_bound 함수 이용)
으로 푼 것 같다.
lower_bound 함수는 저번에도 봤는데 막상 문제를 풀때 생각이 나질 않아 사용하지 못했다.