[BOJ] [JAVA] 18870번 좌표 압축

18870번: 좌표 압축

좌표 압축 문제,,,

주어지는 배열에 대해서 각 배열의 원소를 배열 내의 ranking으로 바꿔서 출력하는 문제이다,,,

처음 생각한 방식은 배열을 입력받고,,,

배열을 set로 다시 받아서 중복 없애고,,,

다시 배열로 변환해서 오름차순 정렬하고,,,

원래 배열에서 for문 돌려서 set애서 변환된 배열에서 원소를 찾아서 index를 뽑아내는 방식이었는데 시간초과됐다,,,

 

답은 HashMap을 사용하는 거였다!

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];
		int [] sortedArr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		HashMap <Integer, Integer> map = new HashMap<>();
		
		for (int i = 0; i < n; i++) {
			arr[i] = sortedArr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(sortedArr);
		
		int rank = 0;
		for (int s : sortedArr) {
			if (!map.containsKey(s)) {
				map.put(s, rank);
				rank++;
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int key : arr) {
			int value = map.get(key);
			sb.append(value).append(" ");
		}
		System.out.print(sb);
		
	}
}

HashMap은 key값에 대응되는 value를 바로 찾을 수 있기 때문에 내가 한 기존 방식의 시간 복잡도인 O(N²)에서 O(N)으로 단축할 수 있다!

 

아! StringBuilder 사용법도 알게 되었다!