18870. 좌표 압축 (자바, Java)

좌표압축이란, 상대적인 값만 비교하기 위해 불필요한 부분을 압축하는 거라 생각하시면 되겠습니다.

각종 파일압축과 비슷한 원리로 작동합니다.

문제에서는 순위개념으로 이해하셔도 되겠습니다. 제일 낮은 숫자가 0순위고, 이후 1순위씩 올라가는 식으로.

 

처음에 이클립스로 풀었지만 시간이 초과되었고, 이후 제가 소개해드렸던 블로그를 통해

HashMap 자료형에 대해 알게되어 풀 수 있었습니다.

HashMap 자료형은, key값과, key값에 대응되는 value값이 있는 자료형입니다. 아직 다양하게 사용해본 것이 아니기 때문에, 설명을 아끼려합니다. 자세한건 이쪽을 참고해주세요!

https://st-lab.tistory.com/279

 

 

 

1. 처음 시도하여 이클립스에서는 성공했으나, 시간초과로 제출에서 실패한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String str1 = br.readLine();
		String[] str2 = str1.split(" ");
		int[] x = new int[n]; // 원본배열
		int[] x2 = new int[n]; // 정렬배열
		
		
		Arrays.sort(x2);
		
		ArrayList<Integer> x3 = new ArrayList<>();
		x3.add(x2[0]);
		
		for (int i=1; i<n; i++) {
			if (x2[i] != x2[i-1]) {
				x3.add(x2[i]);
			}
		}		
		
		StringBuilder sb = new StringBuilder();
		
		for (int i=0; i<n; i++) {
			for (int j=0; j<x3.size(); j++) {
				if (x[i] == x3.get(j)) {
					sb.append(j + " ");
					break;
				}
			}
		}
		
		System.out.println(sb);
	}

}

 

2. HashMap 자료형으로 성공한 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String str1 = br.readLine();
		String[] str2 = str1.split(" ");
		int[] x = new int[n]; // 원본배열
		int[] x2 = new int[n]; // 정렬배열
		HashMap<Integer, Integer> ranking = new HashMap<>();
		
		int rank = 0;
		
		for (int i=0; i<n; i++) {
			x[i] = Integer.parseInt(str2[i]);
			x2[i]=x[i];
		}
		
		Arrays.sort(x2);
		
		for (int i : x2) {
			
			if(!ranking.containsKey(i)) {
				ranking.put(i, rank);
				rank++;
			}			
		}
				
		StringBuilder sb = new StringBuilder();
		
		for (int i : x) {
			int rank2 = ranking.get(i);
			sb.append(rank2 + " ");
		}
				
		System.out.println(sb);
	}

}