[백준/JAVA] 18870: 좌표 압축

[백준/JAVA] 18870: 좌표 압축

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있을 때 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

대충 봤을 때 말이 직관적으로 이해가 되지 않는데, 쉽게 말하면 좌표를 오름차순으로 정렬했을 때 몇번째 순서에 있는가를 묻는 문제이다. 다시 말해 정렬한 후 자신의 앞에 몇개의 숫자가 있는가를 출력한다.

배열에 좌표들을 저장한 후 Arrays.sort()를 통해 정렬하였다. 그리고 HashMap에 좌표와 인덱스를 순서대로 저장하였다. 굳이 HashMap에 또 저장한 이유는 HashMap은 키의 검색이 쉽기 때문이다. 좌표를 입력받은 순서대로 출력해야 하기 때문에 처음에 배열의 복사본을 tmp에 저장해두었고, 마지막에 tmp를 통해 해당 좌표의 순서값을 출력한다.

소스코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws 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[] tmp = new int[n];
		System.arraycopy(arr, 0, tmp, 0, n);
		
		Arrays.sort(arr);
		HashMap<Integer, Integer> map = new HashMap<>();
		int index = 0;
		for(int i=0; i<n; i++) {
			if (map.getOrDefault(arr[i], -1) == -1)
				map.put(arr[i], index++);
		}
		BufferedWriter bw = 
				new BufferedWriter(new OutputStreamWriter(System.out));
		for(int i=0; i<n; i++) {
			bw.write(map.get(tmp[i])+" ");
		}
		bw.flush();
	}
}

실행시간이 생각보다 많이 걸려서 아쉬운 문제이다. 코드를 더 최적화하는 방법이 있을 텐데 다음 번엔 더 짧은 실행속도를 목표로 해봐야겠다.