[정렬] 백준 - 좌표압축

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

18870번: 좌표 압축

 

 

-문제해설

먼저 입력 좌표값들을 배열에 저장하고 이 배열을 복사한다.

복사된 배열을 오름차순으로 정렬한다.

 

그리고 정렬된 배열을 순회하면서 해시맵에 넣어준다.

이때 키는 정렬된 배열의 값이 들어가고 값으로는 좌표압축값인 idx가 들어간다. 

또한 무작정 집어넣는 것이 아니라 해시맵에 똑같은 키가 있을 경우엔 건너뛰게 된다.

 

 

-자바

package sort;

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

public class BJ18870 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		int arr[] = new int[n];
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) arr[i] = Integer.parseInt( st.nextToken() );
		
		int copyArr[] = new int[n];
		copyArr = arr.clone();
		Arrays.sort( copyArr );
		
		HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
		int idx = 0;
		for( int i : copyArr ) {
			if( !m.containsKey(i) ) {
				m.put( i, idx++ );
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for( int i : arr ) sb.append( m.get(i) ).append( " " );
		
		System.out.println( sb );
	}
}

 

-파이썬

n = int( input() )
arr = list( map(int, input().split() ) )
a = list( set(arr) )
a.sort()
d = { val: idx for idx, val in enumerate(a) }
print( " ".join( str(d[x] ) for x in arr ) )