백준 18870 좌표 압축 (JAVA 자바 풀이)

백준 18870 좌표 압축 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

 

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

 

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

⚔ 입력

첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

 

📣 출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

for문을 이중으로 반복해서 사용할시 N의 범위가 100만이므로 1초 + a가 되면서 

시간 제한에 걸려버린다. 

 

이 문제는 중복을 처리하는 과정에서 연산이 많이 든다. 따라서 일반적인 흐름에서 답을 구하기보다는 

sort를 통해 정렬을 해주고 idx를 이용해서 푸는 아이디어가 필요하다. 

 

hashmap을 이용한다. 

 

 

 

 

💡 코드 구현

 

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 Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		int numberOfCoordinates = Integer.parseInt(bufferedReader.readLine());

		int[] coordinates = receiveCoordinates(bufferedReader, numberOfCoordinates);
		int[] coordinatesCopied = coordinates.clone();        // 정렬을 수행하고 order를 구하기위한 copy 배열

		Arrays.sort(coordinatesCopied);

		HashMap<Integer, Integer> orderedNumbers = new HashMap<>();
		int order = 0;
		for (int i = 0; i < coordinatesCopied.length; i++) {
			if (orderedNumbers.containsKey(coordinatesCopied[i])) {
				continue;
			}
			orderedNumbers.put(coordinatesCopied[i], order);
			order++;
		}

		StringBuilder stringBuilder = new StringBuilder();
		for (int number : coordinates) {
			stringBuilder.append(orderedNumbers.get(number)).append(" ");
		}
		System.out.println(stringBuilder);
	}

	private static int[] receiveCoordinates(BufferedReader bufferedReader, int numberOfCoordinates) throws IOException {
		int[] coordinates = new int[numberOfCoordinates];
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i = 0; i < numberOfCoordinates; i++) {
			coordinates[i] = Integer.parseInt(stringTokenizer.nextToken());
		}
		return coordinates;
	}
}

 

 

 

 

 

입력 배열을 받을 때 2차원 배열을 통해 idx를 같이 받는 방식으로 구현하면 copy 없이 idx를 사용할 수 있다. 

이때 앞의 값으로 정렬하면 뒤의 값은 따라온다. 

 

int[][] xs = new int[N][2];
for (int i = 0; i<N; i++){
	xs[i][0] = Integer.parseInt(bufferedReader.readLine());
	xs[i][1] = i; 
}

Arrays.sort(xs, new Comparator<int[]>(){
	@Override
    public int compare(int[] o1, int[] o2){
       return o1[0] - o2[0];
    }
});