[백준 / BOJ] 18870번 좌표 압축 (Python C++)

문제 링크 : 18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

 

🖥️ 시작하며

문제를 대충 해석하면 어려울 수 있는 문제다. 찬찬히 뜯어보자.

좌표 압축을 수행하려고 하는데, 조건은 아래와 같다.

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

주어진 예시로 보자.

1. 2 4 -10 4 -9 가 입력으로 주어진다.
2. Xi 를 좌표 압축한 결과인 X'i 의 값은, 즉 인덱스 0의 2 는
3. Xi > Xj 를 만족하는데, 만족하는 Xj 의 개수와 같아야 한다.

→ 예시에서 2 는 -10, -9 보다 크므로 2 로 변환되어야 한다.
→ 예시에서 4 는 -10, -9, 2 보다 크므로 3 으로 변환되어야 한다.

논리를 차근차근 따라가면 쉽다.

이제 구현해야 하는데, 입력 조건이 굉장히 괴랄하다. 일단 일반적인 방식으로는 시간 초과가 날 것 같다. 그렇다면 좀 다르게 접근해야 할 필요가 있다.

잘 생각해보라는 말은 싫다. 하지만 알고리즘은 결국 아이디어 싸움이고, 누가 더 번뜩이는 아이디어를 더 빨리 떠올리냐의 싸움인 것 같다. 이 문제도 비슷하다. 쉬운 편에 속하지만, 이 문제는 집합을 활용해야 한다.

앞선 조건 중에서 3번을 잘 보면, 입력받은 배열을 정렬한 후 해당 숫자의 인덱스 값과 같다고 볼 수 있다.

• 2 4 -10 4 -9 를 정렬하면 -10 -9 2 4 4 가 된다.
• 생각해보자. -10 은 0, -9 는 1 , 2 는 2 , 4 는 3 . 각각의 인덱스 값이다. 이를 순서대로 배열하면, 그 자체가 좌표 압축이 된다.

그렇다면 구현해보자.

Python

import sys

sys = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    inputArr = list(map(int, input().split()))
    index_dict = {value: index for index, value in enumerate(sorted(set(inputArr)))}

    print(*(index_dict[i] for i in inputArr))

C++

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

using namespace std;

void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main() {
    int N;
    cin >> N;

    vector<int> v(N);

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

    vector<int> temp_v(v);
    sort(temp_v.begin(), temp_v.end());

    temp_v.erase(unique(temp_v.begin(), temp_v.end()), temp_v.end());

    for (int i = 0; i < N; i++) {
        auto it = lower_bound(temp_v.begin(), temp_v.end(), v[i]);
        cout << it - temp_v.begin() << ' ';
    }

    return 0;
}

 

소감

오랜만에 알고리즘 풀려니까 너무 어려웠다.

부록

참고문헌

---

[백준] 18870번 좌표 압축 - C++ - DGOS | 동꿀오소리