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

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

18870번: 좌표 압축

 

문제 접근

각 인덱스가 자기 보다 작은 값들의 수를 값으로 갖고 있어야한다.

 

그래서 배열을 정렬시키면 0번 인덱스는 자신이 제일 작기 때문에 0을 가지고, 1번 인덱스는 0번 인덱스보다 크기에 1을 가진다.

이렇게 쭉 진행하면 인덱스 순서가 값이 되는데 중복인 수를 갖고 있으면 중복인 수들이 갖는 값도 같아야 한다.

이 때 정렬된 배열을 HashMap에다 넣으면 Map에서 중복을 걸러준다.

 

하지만 Map에서 중복되는 key에 value를 넣으면 뒤에 들어간 value로 덮여쓰여지기 때문에 앞서 들어간 key가 있는지

containsKey()로 확인하고 map에 값을 넣어준다.

map에 값을 다 넣었으면 이후에 원본(origin) 배열의 인덱스를 map에 넣고 출력하면 된다.

 

++ 코드를 직접 읽는 게 더 이해될 듯하다.

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[] origin = new int[N];
		int[] sort = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<origin.length; i++) {
			origin[i] = Integer.parseInt(st.nextToken());
			sort[i] = origin[i];
		}
		
		// 배열을 정렬해서 해당 값들로 배열을 만들면 중복 숫자들은 걸러지지 않을까
		Arrays.sort(sort);
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		int count = 0; // 순서 정하는 변수
		for(int n : sort) {
			if(!map.containsKey(n)) { // 같은 인덱스가 또 나오면 뒷 숫자가 새로 덮여지기 때문에
				map.put(n, count);
				count++;
			}
		}
		
		StringBuilder sb = new StringBuilder(); // 반복문 내에서 일일이 출력하면 시간초과 걸리더라
		for(int n : origin) { // 기존 배열 인덱스에 순서 값 넣기
			int num = map.get(n);
			sb.append(num).append(" ");
		}
		
		System.out.println(sb);
	}
}