[boj18870/Java]좌표 압축(HashMap)

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

18870번: 좌표 압축

 

정렬..? 자료구조..? Set..? HashMap..? 

뭘 써야할지 많은 고민을 했던 문제였다.

 

그래서 일단 해야할 일을 정리해봤을 때 다음과 같이 생각할 수 있었다.

1. 원래 배열을 정렬한다.

2. 순서에 맞춰서 중복되지 않도록 값을 매칭해준다.

여기서 중복되지 않도록 값을 매칭한다는 부분에서 hashMap을 이용해서 문제를 해결해야겠다고 생각했다.

 

자바에서 map은 HashMap, HashTable(HashMap 사용을 권장), TreeMap이 있는데 간단히 HashMap을 이용해 구현했다.

Map은 중복되지 않는 key 값에 대하여 value값을 쌍으로 매칭하는 자료형으로 순서에 관계 없이(순서를 신경쓰려면 LinkedHashMap을 사용) 즉 index가 아닌 key 값으로 value를 얻는다.

Java에서의 HashMap 사용은 다음과 같다.

1. 선언

HashMap<Integer, Integer> sortHash = new HashMap<Integer, Integer>();
//HashMap<Integer, Integer> sortHash = new HashMap<>(); //선언부 자료형 생략 가능

2. 주요 함수

기능	함수	리턴
key-value 쌍 삽입	put	void
key값으로 조회	get	value 값 리턴
key-value 쌍 삭제	remove	삭제된 value 값 리턴
모든 값 삭제	clear	void
value 수정	replace	바뀐 value 값 리턴
모든 key 조회	keySet	key의 집합 리턴
모든 key-value 쌍 조회	entrySet	key-value 집합 리턴

그래서 이러한 HashMap을 이용해서 문제를 풀기 위해서 앞서 이야기한 두 가지 주요 기능을 구현해야했다.

1. 원래 배열을 정렬한다.

2. 순서에 맞춰서 중복되지 않도록 값을 매칭해준다.

 

두개의 배열(origin, sorted)를 이용해서 초기 배열을 유지하면서 정렬된 배열도 선언했다.

배열의 정리는 간단히 Arrays.sort를 이용했다.

이후 sorted를 기준으로 HashMap에 없는 key값을 추가하면서 rank를 1씩 늘려주면

각각의 key값이 오름차순으로 증가하는 value 값을 가질 수 있다.

 

마지막으로 key값을 기준으로 출력을 하면 끝!

 

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());

		int[] origin = new int[N];
		int[] sorted = new int[N];
		HashMap<Integer, Integer> sortHash = new HashMap<Integer, Integer>();

		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<N; i++) {
			sorted[i] = origin[i] = Integer.parseInt(st.nextToken()); 
		}
		
		Arrays.sort(sorted);
		
		int rank = 0;
		for(int i:sorted) {
			if(!sortHash.containsKey(i)) {
				sortHash.put(i, rank);
				rank++;
			}
		}
		
		for(int k: origin) {
			sb.append(sortHash.get(k)).append(' ');
		}
		
		System.out.println(sb);
		
	}

}