[백준알고리즘-JAVA]18870번 풀이(좌표 압축) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 18870번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 18870 (좌표 압축)

문제

수직선 위에 N개의 좌표 X1, X2,..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2,..., XN에 좌표 압축을 적용한 결과 X'1, X'2,..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

 

둘째 줄에는 공백 한 칸으로 구분된 X1, X2,..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2,..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109

입력 예시

5
2 4 -10 4 -9

출력 예시

2 3 0 3 1

입력 예시

6
1000 999 1000 999 1000 999

출력 예시

1 0 1 0 1 0

성공 코드

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 IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 StringBuilder sb = new StringBuilder();
	   	  
	   	 	int num = Integer.parseInt(br.readLine());
	   	 	
	   	 	String[] arr = br.readLine().split(" ");
	   	 	int[] an = new int[num];
	   	 	int cnt = 0;

	   	 	for(int i = 0 ; i < arr.length ; i ++)
	   	 		an[i] = Integer.parseInt(arr[i]);
	   	 	
	   	 	int[] temp = an.clone();
	   	 	
	   	 	Arrays.sort(an);
	   	 	
	   	 	HashMap<Integer, Integer> hmap = new HashMap<>();
	   	 	for(int i = 0 ; i < an.length ; i++) {
	   	 		if(!hmap.containsKey(an[i]))
	   	 			hmap.put(an[i], cnt++);
	   	 	}
	   	 	
	   	 	for(int i = 0; i < num ; i++) {
	   	 		sb.append(hmap.get(temp[i])).append(" ");
	   	 	}
	   	 	
	   	 	System.out.println(sb.toString());
	}
}

좌표 입력 알고리즘은 저 같은 경우 처음에 문제가 무엇을 의미하는지 이해 못했습니다... ㅎㅎ

 

자세히 보니 입력으로 주어진 숫자를 서로 비교하여 자기보다 작은 수를 세는 알고리즘 이더라고요

 

첫 번째 입력은 2 4 -10 4 -9의 숫자를 입력으로 받았는데

 

이 같은 경우를 보면 2보다 작은 수는 -10 -9 이에 따라 2의 숫자가 출력돼야 하는 것이죠

 

문제를 이해했다면, 이제 이를 해결해야 하는데 사실 저도 처음 알고리즘을 풀이할 때, 단순 반복문으로 count를 하였더니 

 

입력 예시 2번째에서 3 0 3 0 3 0이라는 값이 출력되었죠. 중복을 생각하지 못했습니다. 한참을 헤매다 결국 hashmap을 이용하여 풀이하는 법을 알게 되었죠..

 

방법을 알면 풀이는 생각보다 간단해집니다. 사용하는 기술은 어렵지 않은데, 알고리즘을 풀이하는 사고를 하기가 어려웠죠. 오늘도 하나를 배우고 갔습니다 ㅎㅎ. 아래 STEP을 따라가시면서 코드를 해석해드리겠습니다 ~

 

---

알고리즘 흐름도

입력받기 -> 받은 입력 배열에 넣기 -> TEMP배열을 생성하기 -> 기존 배열 정렬하기 -> 기존 배열을 이용하여 COUNT 하기 -> 출력하기

---

STEP1 입력 배열에 넣기

			int num = Integer.parseInt(br.readLine());
	   	 	
	   	 	String[] arr = br.readLine().split(" ");
	   	 	int[] an = new int[num];

	   	 	for(int i = 0 ; i < arr.length ; i ++)
	   	 		an[i] = Integer.parseInt(arr[i]);

입력받는 것은 사실 너무 쉽죠?? br.readLine의 경우 저는 BufferedReader을 이용하여 입력받았기 때문입니다. System을 사용해도 무관합니다 ~

---

STEP2 입력 정렬하기 & temp배열 만들기

int[] temp = an.clone();
	   	 	
Arrays.sort(an);

여기서 의문점을 2개일 것입니다. 

 

 - 왜 temp를 만드냐

기존에 받았던 입력을 an으로 넣어주었습니다. 그러나 해당 알고리즘을 풀이하기 위해서는 정렬된 배열과 입력 그대로 받은 배열 2개가 필요하기 때문입니다. 이에 대한 이해는 아래 STEP 3, STEP 4를 보시면 더욱 이해가 쉽습니다.

 

 - clone은 무엇인가

clone은 배열을 쉽게 복사해주는 메서드입니다. 물론 타입이 다르면 안 됩니다 ~

---

STEP 3 Hashmap 이용하여 count 하기

HashMap<Integer, Integer> hmap = new HashMap<>();
	   	 	for(int i = 0 ; i < an.length ; i++) {
	   	 		if(!hmap.containsKey(an[i]))
	   	 			hmap.put(an[i], cnt++);
	   	 	}

해당 알고리즘의 핵심이죠 의문점을 하나씩 풀어드리겠습니다.

 

 - hashmap이 무엇이냐

hashmap을 깊게 알기보다는 쉽게 이해하기 쉽게 인덱스 대신 key를 사용한 배열이라고 생각하시면 됩니다. 기존에 알던 배열은 0 ~ 시작한 번호라면 우리가 key를 통해서 a, b, c 이런 문자는 숫자 등으로 표현할 수 있는 배열입니다.

 - containsKey가 무엇이냐

해당 메서드는 hashmap에 있는 메서드로 해당 배열에서 key값이 (an [i])와 같은 게 있으면 true 없으면 false를 반환해주는 메서드입니다.

 - put이 무엇이냐

hashmap에 배열을 추가하는 메서드로 an [i]를 key로 사용하고 cnt++을 value로 사용합니다.

 - 전체적인 코드 설명

입력 예시는 2 4 -10 4 -9로 들겠습니다.

 

해당 입력 배열을 앞서 저희는 정렬을 했습니다. 이에 따라

an 배열에서는 -10 -9 2 4 4라는 순서로 저장되어있겠죠?

 

코드를 따라가 봅시다. 맨 처음 hmap에는 아무것도 없으니 당연히 if문에 걸리지 않겠죠??

 

그러면 key = -10 value = 0이라는 값이 들어가게 되고 후에 cnt = 1로 바뀌게 됩니다. (후위 연산자이기 때문에)

그다음 반복에서는 key = -9 value = 1이라는 값이 들어가고 후에 cnt =2로 바뀌게 됩니다.

그다음 반복에서는 key = 2 value = 2이라는 값이 들어가고 후에 cnt =3로 바뀌게 됩니다.

그다음 반복에서는 key = 4 value = 3이라는 값이 들어가고 후에 cnt =4로 바뀌게 됩니다.

그 다음 반복에서는 이미 key가 4인 값이 들어가 있기 때문에 조건문이 실행되지 않고 해당 반복문이 끝나게 됩니다. 결국 hashmap에는 아래와 같이 값이 할당됩니다.

key	-10	-9	2	4
value	0	1	2	3

 

---

STEP 4 출력하기

for(int i = 0; i < num ; i++) {
	   	 		sb.append(hmap.get(temp[i])).append(" ");
	   	 	}
	   	 	
	   	 	System.out.println(sb.toString());

이번 출력은 조금 생각하셔야 될 것이 바로 어떤 값을 가져오냐! 바로 STEP2에서 의문이었던 TEMP를 만든 이유!! 저희가 출력해야 하는 순서는 엄연히 입력받은 순서입니다. 그런데 저희가 임의로 정렬하여 순서를 바꾸었으니 그 순서를 기억하는 배열이 필요했기 때문입니다.

 

이에 따라 저희가 원하는 순서는 temp배열의 순서. temp배열은 여전히 2 4 -10 4 -9 의순 서로 저장되어 있죠.

 

 - 여기서 get은 해당 key에 있는 value를 가져오는 메서드

 

이에 따라 2 값에는 value 값이 2

4 값에는 value 값이 3

-10 값에는 value 값이 0

4 값에는 value 값이 3

-9 값에는 value 값이 1

값들이 출력되게 됩니다.