[Python][C++] 18870번 좌표 압축

문제

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

 

 

 

 

코드

1. Python

n = int(input())  # 배열의 크기를 입력받음

arr = list(map(int, input().split()))  # n개의 정수를 입력받아 리스트로 저장
arr2 = sorted(set(arr))  # 중복을 제거하고 정렬하여 순서를 정함

# 각 값에 대해 해당 값이 정렬된 리스트에서 몇 번째인지 저장하는 딕셔너리 생성
dic = {arr2[i]: i for i in range(len(arr2))}

# 입력받은 배열의 각 원소에 대해 압축된 좌표를 출력
for i in arr:
    print(dic[i], end=' ')

 

2. C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;  // 입력받을 정수의 개수

    vector<int> x;  // 입력된 정수를 저장할 벡터

    // 입력된 정수를 벡터에 저장
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        x.push_back(num);
    }

    vector<int> copy = x;  // 정렬을 위한 복사본 생성

    sort(copy.begin(), copy.end());  // 복사본 정렬

    unordered_map<int, int> mp;  // 숫자에 대한 압축 결과를 저장할 맵
    int mapping = 0;  // 압축된 숫자를 나타낼 인덱스

    // 정렬된 배열을 이용해 압축된 좌표를 매핑
    for (auto num : copy) {
        if (mp.find(num) == mp.end())  // 맵에 해당 숫자가 없다면
            mp[num] = mapping++;  // 숫자에 대해 압축된 인덱스를 매핑
    }

    // 원래 배열에 대해 압축된 결과를 출력
    for (auto num : x) {
        cout << mp[num] << " ";  // 압축된 좌표 출력
    }

    return 0;
}

 

 

풀이

1. 정렬을 이용한 압축:
   • 주어진 좌표 리스트를 정렬한 뒤, 각 좌표의 고유한 순위를 매긴다.
   • 이 순위는 중복된 값을 고려하여, 같은 좌표는 같은 압축된 값을 갖도록 한다.
2. 구현:
   
   • 정렬된 좌표 리스트를 순회하면서 각 좌표의 압축된 순위를 매긴다.
   • 원래의 좌표 리스트에서 각 좌표를 압축된 순위로 변환하여 출력한다.