자바 백준 18870번 문제 : 좌표 압축

문제 출처 : https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

문제 : 

 

풀이 :

입력받은 원래 값들의 배열을 그대로 저장하는 arr 배열,

오름차순으로 정렬할 sortArr 배열을 만들고 

두 배열에 입력받는 좌표를 저장한다. 

이후 sortArr 배열을 오름차순 정렬하고,

압축 전의 값과 압축 후의 값을 각각 key와 value로 저장하는 HashMap을 생성한다.

그리고 arr 배열에서 for문을 돌려 HashMap을 이용해 각 좌표(key)에 대한 압축된 좌표(value) 를 꺼내와 출력한다.

 

소스코드 :

import java.util.*;
import java.io.*;
public class Main {
	public StringBuilder solution(int n, int[] arr, int[] sortArr) {
		StringBuilder sb = new StringBuilder();
		HashMap<Integer, Integer> map = new HashMap<>();
		Arrays.sort(sortArr);
		int cnt = 0;
		for(int key : sortArr) {
			if (!map.containsKey(key)) {
				map.put(key, cnt);
				cnt++;
			}
		}
		for(int key : arr) {
			sb.append(map.get(key)).append(" ");
		}
		return sb;
	}
	public static void main(String[] args) throws IOException {
		Main T = new Main();
		//Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] sortArr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for (int i=0; i<n; i++) {
			arr[i] = sortArr[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		System.out.println(T.solution(n, arr, sortArr));
	}
}