[BOJ] 18870: 좌표 압축

문제 소개

2020.04.11 기준,  solved.ac 실버 2티어 문제입니다.

 

문제 제목 그대로 좌표 압축을 하는 문제입니다.

좌표 압축은 사실 map 혹은 dictionary (언어에 따라 다름) 등을 알면 쉬운 문제입니다.

 

문제 링크

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

18870번: 좌표 압축

아이디어

이 문제는 정말 친절하게도, 제목이 곧 문제입니다.

근데, 좌표 압축을 처음 접하는 사람이 있을 수도 있으니 설명을 해보자면..

 

문제의 예시를 그대로 가져와볼까요?

5
2 4 -10 4 -9

이 예시에서 사용된 좌표는 -10, -9, 2, 4 정도가 있군요.

 

사용는 좌표들을 만약에 배열에 하나 하나 표시한다면 아래 그림과 같이 적어도 10여칸의 배열이 필요합니다.

배열 index 기반으로 저장할 때

한번 map(map 혹은 dictionary에 대한 것은 나중에 다루겠습니다.)으로 저장한다면 아래 그림과 같이 

중복되지 않는 좌표의 개수만큼만 저장합니다.

map 이라고 생각하시죠 아무튼 map임.

 0부터 좌표 압축을 해야 한다는 점이 명시는 안 되어있지만, 예시 상으로 알 수 있으므로 0 부터 좌표 압축을 하면 되겠죠? 물론 좌표 압축을 하기전에 문제의 조건에 따라 sorting을 하고 중복을 제거해야 합니다. :)

 

코드(python)

n = int(input())
L = list(map(int,input().split()))
A = list(set(L[:]))
d = {}
A.sort()
for i in range(len(A)):
    d[A[i]] = i
for i in L:
    print(d[i],end = " ")

코드(cpp)

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int ar[1100000];
int b[1100000];
map <int, int> m;
int n;
int cnt;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int x=0; x<n; x++) {
        cin >> ar[x];
        b[x] = ar[x];
    }
    sort(b,b+n);
    m[b[0]] = cnt++;
    for(int x=1; x<n; x++) {
        if(b[x] != b[x-1]) {
            m[b[x]] = cnt++;
        }
    }

    for(int x=0; x<n; x++) {
        cout << m[ar[x]] << " ";
    }
    
}

Rmx