BOJ 18870 (S2) 좌표 압축

문제 요약

주어진 N개의 1차원 좌표값(X)을 대소 비교하여 좌표를 압축해 보자.
(단, 대소 판단에 필요하지 않은 크기 비교는 하지 않는다.)

풀이 방향

실제로 지도에서 축척을 할 때는 실제 크기에 비례하게끔 같은 비율로 압축하지만, 지금 문제가 원하는 바는 그것이 아니다.

가장 작은 좌표값을 0으로 설정하고, 나머지 좌표값은 단순한 대소 비교를 통해 몇 번째로 작은지 변환하면 된다.

예를 들어, [1 2 1 4]의 경우 1<2<4 이므로 [0 1 0 2]로 변환하면 된다는 뜻이다.

제출 답안

#include <iostream>
#include <vector>
#include <algorithm> //pair, sort
using namespace std;

int main() {
    int n; cin >> n;
    vector<pair<int,pair<int,int>>> v(n); // <압축된 좌표값, <실제 좌표값, 순서>>
    for(int i=0; i<n; i++) {
        cin >> v[i].second.first;
        v[i].second.second=i;
    }
    sort(v.begin(),v.end()); //좌표값이 작은 순으로 정렬
    v[0].first=0;
    for(int i=1; i<n; i++)
        if(v[i].second.first==v[i-1].second.first)
            v[i].first=v[i-1].first;
        else
            v[i].first=v[i-1].first+1;
    for(int i=0; i<n; i++) {
        v[i].second.first=v[i].first;
        v[i].first=v[i].second.second;
    }
    sort(v.begin(),v.end()); //좌표 순서대로 정렬
    for(int i=0; i<n; i++)
        cout << v[i].second.first << ' ';
    return 0;
}

답안 해설

우선 입력값을 저장하고 가공하기 위해 벡터를 선언한다. 나중에 출력할 때 입력받은 순서가 중요하기 때문에, 벡터를 여러개 선언하거나 pair, tuple 등의 형태로 선언해주면 좋다.

나는 처음에 pair를 이중으로 사용하여 <압축된 좌표값, <실제 좌표값, 순서>> 형태로 벡터를 선언했다.
이때 처음에는 압축값을 모르므로 전부 0으로 초기화했다.

pair의 정렬은 pair의 원소들을 차례대로 비교하면서 진행된다.
나처럼 pair<int,pair<int,int>>; 형태로 선언했다면
1. pair.first
2. pair.second.first
3. pair.second.second
순서로 우선해서 정렬된다.

즉, [1,0,2][1,0,3] [1,1,2][2,0,0]이 있을 경우, pair.first 값인 1,2부터 정렬하고, pair.first 값이 같은 [1,0,2][1,0,3] [1,1,2]는 pair.second.first를 비교하면서 다시 정렬한다는 의미이다. 같을 경우 마찬가지로 pair.second.second를 비교,정렬하며 마친다.

이렇게 첫 번째 정렬에서는 pair.first값이 모두 0으로 같으므로, pair.second.first값인 좌표값을 대소 비교하여 새로운 압축값을 pair.first에 할당한다.

대소 비교를 마치면, 입력받았던 순서대로 압축값을 출력하기 위해 순서인 pair.second.second 값을 pair.first 로 옮기고 정렬한다. (출력할 압축값 pair.fisrt는 미리 pair.second.first로 옮긴다. 이때 처음에 입력받았던 좌표값은 더이상 사용하지 않으므로 무시해도 좋다.)

pair를 오름차순, 내림차순, 사용자정의함수로 정렬하는 방법에 대해 알아보고 목적에 맞게 잘 활용하는 것이 좋다.

특히 pair.first는 오름차순, pair.second는 내림차순 등 앞/뒤를 다른 방식으로 정렬하는 문제도 많기 때문에 적절히 사용할 수 있도록 다양한 방법을 찾아보면 좋다.

이 문제와 관련된 좋은 문제
BOJ 11650 (S5) 좌표 정렬하기
BOJ 11651 (S5) 좌표 정렬하기 2
BOJ 10814 (S5) 나이순 정렬

추가로 읽어보면 좋은 내용

• vector와 pair
• pair 여러 개 사용해 보기
• algorithm-sort로 정렬해보기