좌표를 압축하는 알고리즘 JAVA / C++ / 파이썬

알고리즘 대회에서 좌표를 압축하는 아이디어는 많이 활용됩니다.

주어진 숫자를 압축해서 작은 용량과 작은 숫자 범위로 표현하는 것입니다.

 

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

18870번: 좌표 압축

매우 쉬운 좌표 압축 문제가 있습니다.

백준 18870번 좌표 압축을 풀어봅시다.

 

 

수직선위의 좌표는 매우 큰 범위를 갖습니다.

숫자도 100만개로 많습니다. (빠른 대량 입출력은 기본입니다.)

 

바로 떠오르는 아이디어는 아래와 같습니다.

1) 배열을 정렬

2) 가장 작은 숫자를 0으로, 1씩 증가하며 매핑

3) 최초 배열을 하나씩 확인하면서 숫자(순위)를 출력

 

1. JAVA

최초 입력받은 배열을 유지하고 정렬할 배열을 만들기 위해,

.clone() 함수로 깊은 복사를 진행합니다.

 

해쉬 맵을 선언하여 숫위를 매핑합니다.

최초 입력받은 배열에서 숫자를 하나씩 확인하면서 순위값을 찾아 append하고 한번에 출력합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());

		int[] a = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++){
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] aSort = a.clone();
		Arrays.sort(aSort);
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int mapCount = 0;
		
		for(int i = 0; i < aSort.length; i++) {
			if(!map.containsKey(aSort[i])){
				map.put(aSort[i], mapCount);
				mapCount++;
			}
		}
		
		for(int i = 0; i < a.length; i++) {
			bw.append(map.get(a[i]) + " ");
		}
		bw.flush();
	}
}

2. C++

자료구조를 잘 활용한다면 매우 쉬운 문제입니다.

JAVA와 똑같이 풀면 재미가 없으니, 깊은 복사를 위해 처음부터 입력을 두 개의 벡터에 받습니다.

소팅을 하되 중복값을 제거합니다.

값을 찾아 순위를 출력합니다.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    int temp;
    vector<int> a, aSort;

    for(int i = 0; i < N; i++) {
        cin >> temp;
        a.push_back(temp);
        aSort.push_back(temp);
    }
        
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()),a.end());
    for(int i = 0; i < N; i++) {
        cout << lower_bound(a.begin(), a.end(), aSort[i]) - a.begin() << " ";
    }
    return 0;
}

3. Python 파이썬

파이썬 역시 동일한 아이디어로 접근합니다.

 

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
aSort = list(sorted(set(a)))
cnt = {aSort[i]: i for i in range(len(aSort))}
for i in a:
    print(cnt[i], end = ' ')

시간복잡도는 정렬하는데 O(NlogN),

순위를 찾는데 O(1) ~ O(logN)로 접근한다는 생각으로 풀이합니다.