[JAVA] 백준 18870번 좌표압축 : HashMap (임의접근)

18870번: 좌표 압축

 

1. 문제 추상화

 

수열이 주어졌을 때 각각의 수보다 작은 서로 다른 수의 개수를 입력받은 순서대로 출력하시오. 

 

2. 알고리즘

 

1. HashMap

 

조금 난해한 문제였다. 입력받은 순서대로 결과를 출력해야 했기에 원본용 배열과 정렬용 배열 두 가지를 만들었다. 그렇다보니 출력과정에서 두 개의 배열을 탐색해야했고 시간복잡도는 O(n²)이 되어 시간초과가 발생했다. 그래서 인터넷에서 방법을 찾던 중 HashMap 자료구조를 발견하였다. 

 

HashMap은 key-value 구조이다. key를 해싱연산하여 생성된 인덱스 주소가 가리키는 HashMap 내부배열에 value 값을 저장하는 방식으로 key값을 안다면 해싱을 통한 '임의접근(Random-Acess)'이 가능하다. 그러므로 시간복잡도는 O(1)이 된다. 내가 했던 방식은 순차접근으로 시간복잡도가 O(n)이다. 두 개의 배열을 순차접근했으니 시간복잡도가 O(n²)이 나온 것이다. 

 

[자료구조] HashMap 파헤치기 1 (Linked List + Red Black Tree)

( HashMap에 대한 자세한 내용은 위 포스팅을 참고해주세요!)

 

 

2. 서로 다른 작은 수의 개수

 

인덱스	0	1	2	3	4
값	-5	3	7	8	11

 

배열을 정렬하면 서로 다른 작은 수의 개수는 쉽게 구해진다. 바로 인덱스가 그것을 나타낸다.  7의 인덱스는 2이다. 그리고 7보다 작은 서로 다른 수의 개수는 0과 1이다. 

 

3. 알고리즘

 

1. 원본용 배열 만들기

2. HashSet을 통해 중복이 제거된 정렬용 배열 만들기

3. Quick 정렬 or Merge 정렬로 정렬하기

4. 정렬용 배열의 인덱스를 HashMap의 Value로 수를 HashMap의 Key로 저장하기

5. 원본용 배열의 수를 Key로 사용하여 HashMap의 get() 메소드를 통해 Value값 얻기

 

 

3. 코드

// 퀵정렬 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {
	
	private static BufferedReader br;
	private static BufferedWriter bw;
	private static StringBuilder sb;
	private static StringTokenizer stz;
	
	private static int[] originalArr;
	private static int[] sortArr;
	private static HashSet<Integer> hs;
	private static HashMap<Integer,Integer> bridge;
	
	public static void main(String[] args) throws IOException {
		initializeIO();
		makeArr();
		doQuickSort(0,sortArr.length-1);
		setHashMap();
		printArr();
		closeIO();
	}
	
	public static void initializeIO() {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
	}
	
	public static void makeArr() throws IOException {
		int size = getSize();
		originalArr = new int[size];
		hs = new HashSet<Integer>();
		stz = new StringTokenizer(br.readLine());
		
		for(int i=0; i<size; i++) {
			int value = Integer.parseInt(stz.nextToken());
			originalArr[i] = value;
			hs.add(value);
		}
		
		sortArr = new int[hs.size()];
		int i = 0;
		
		Iterator<Integer> iterator = hs.iterator();
		while(iterator.hasNext()) {
			int value = iterator.next();
			sortArr[i++] = value;
		}
	}
	
	public static void setHashMap() {
		bridge = new HashMap<Integer,Integer>();
		for(int i =0; i < sortArr.length; i++) {
			bridge.put(sortArr[i], i);
		}
	}
	
	public static int getSize() throws IOException {
		stz = new StringTokenizer(br.readLine());
		return Integer.parseInt(stz.nextToken());
	}
	
	public static void doQuickSort(int leftIndex, int rightIndex) {
		int leftPointer = leftIndex;
		int rightPointer = rightIndex;
		int pivot = sortArr[(leftIndex+rightIndex)/2];
		
		while(leftPointer <= rightPointer) {
			while(sortArr[leftPointer] < pivot) leftPointer++;
			while(sortArr[rightPointer] > pivot) rightPointer--;
			
			if(leftPointer <= rightPointer) swap(leftPointer++,rightPointer--);
		}
		
		if(leftIndex < rightPointer) doQuickSort(leftIndex,rightPointer);
		if(leftPointer < rightIndex) doQuickSort(leftPointer,rightIndex);
	}
	
	public static void swap(int leftPointer, int rightPointer) {
		int tmpValue = sortArr[leftPointer];
		sortArr[leftPointer] = sortArr[rightPointer];
		sortArr[rightPointer] = tmpValue;
	}
	
	
	public static void printArr() throws IOException {
		sb = new StringBuilder();
		for(int key : originalArr) {
			sb.append(bridge.get(key)+"").append(" ");
		}
		bw.write(sb.toString());
		bw.flush();
	}
	
	public static void closeIO() throws IOException {
		bw.close();
		br.close();
	}
}