[백준] 18870번 좌표 압축 C++ 풀이

---

알고리즘 분류

• 정렬
• 값 / 좌표 압축

---

문제 설명

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

---

입력 설명

첫째 줄에 N이 주어진다.

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

---

출력 설명

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

---

예제 입력

5
2 4 -10 4 -9

 

6
1000 999 1000 999 1000 999

---

예제 출력

2 3 0 3 1

 

1 0 1 0 1 0

---

아이디어

n * 3 벡터를 생성해서 0번째에는 입력받은 값, 1번째에는 입력 받은 순서을 저장한 후

0번째 값을 기준으로 오름차순 정렬한다.

그러면 낮은 값이 앞으로 오므로 압축 좌표가 내 순서가 되고 이를 2번째에 저장한다.

이후 입력 받은 순서를 기준으로 오름차순 정렬한다.

2번째에 저장해놓은 값을 출력한다.

---

알고리즘

n * 3 벡터를 생성해서 첫 번째에는 입력받은 값, 두 번째에는 입력 받은 순서을 저장한 후

0번째 값을 기준으로 오름차순 정렬한다.

0 ~ n-1까지 반복문을 도는데 현재 내 값과 바로 전의 값이 동일하다면 압축 좌표 값을 동일하게 저장하고 아니라면 1씩 압축 좌표 값을 증가시키면서 벡터의 세 번째 칸에 저장한다.

이후 벡터의 두 번째 값 즉, 원래 입력 받은 순서를 기준으로 오름차순 정렬한다.

이루 0 ~ n-1까지 세 번째 칸의 값을 모두 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int>&vec1,vector<int>&vec2)
    {
        return vec1[1]<vec2[1];
    }
int main() {
    int n,j=0;
    cin>>n;
    vector<vector<int>> vec(n,vector<int>(3,0));
    for(int i=0;i<n;i++)
        {
            cin>>vec[i][0];
            vec[i][1] = i;
        }
    sort(vec.begin(), vec.end());
    for(int i=0;i<n;i++)
        {
            if(i == 0) 
            {
                vec[i][2] = j;
                j++;
                continue;
            }
            if(vec[i][0] == vec[i-1][0]) j--;
            vec[i][2] = j;
            j++;
        }
    sort(vec.begin(), vec.end(), compare);
    for(auto a : vec)
        cout<<a[2]<<" ";
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/18870

sort함수에서 커스텀 비교 함수 compare를 따로 선언해서 정렬해본 경험이 적어서 처음에는 좀 햇갈렸지만

이제는 완벽하게 compare를 사용하는 방법을 이해했다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!