[BOJ/백준][Silver2] 18870 : 좌표 압축 (C++)

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

18870번: 좌표 압축

 

 

[난이도] Silver2
[유형] 좌표압축

[풀이]
나올 수 있는 수자의 범위는 -10^9 ~ 10^9이지만 실제 숫자의 개수는 10^6 최대이므로
0~(10^6)-1 로 압축이 가능합니다.
정렬을 한 뒤, map을 이용하였습니다.
작은 수부터 순회하면서 숫자가 이미 map에 저장되어 있다면 이전 수와 동일한 수이므로
mp[a[i]] = k 로 저장해주고, map에 저장되어 있지 않다면 처음 등장하는 수이므로 mp[a[i]] = ++k와 같이
저장해줍니다.
그 뒤 정렬하지 않은 original 배열인 b를 순회하면서
mp[b[i]]를 출력하면 압축된 좌표로 출력이 됩니다.

 

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int mxN = 1e6+1;
int n,a[mxN],b[mxN],k;
map<int,int> mp;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++) mp[a[i]]= mp.find(a[i])==mp.end() ? ++k : k;
    for(int i=0;i<n;i++) printf("%d ",mp[b[i]]-1);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/18870.cpp