[백준] '좌표 압축' - Java

<문제 제시>

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

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

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

<문제이해>
랭킹 알고리즘과 유사하다.
1. 낮은 값이 높은 순위를 갖는다. (가장 높은 순위는 0순위다.)
2. 중복되는 원소는 같은 순위를 갖는다.
3. 낮은 값이 높은 순위를 갖는다는 것, 결국 순위를 정한다는 것은 오름차순으로 '정렬'을 했을 때
첫 번째 인덱스에 있는 원소가 가장 높은 순위를 갖고, 
반대로 가장 마지막에 있는 원소가 가장 낮은 순위를 갖는다는 것을 의미

4. 여기서 우리는 순위를 매겨야하므로, 중복되지 않으면서 각 원소에 대한 순위를 매길 수 있는 자료구조인 
HashMap자료구조를 활용

Example)
입력 : 2 4 -10 4 -9
출력 : 2 3   0 3  1

<예시 입출력>

---

<문제 해결 과정>

이러한 좌표압축 문제는 큰 데이터의 범위나 단순화 할 일들에 주로 쓰이는데, GPS 좌표 압축같이 2차원 혹은 3차원 데이터를 그리드로 놓고 보았을 때 데이터 값들을 단순화하여 압축하는 방식 등이 있다.

---

Answer 1) 

for(int k : copy) {
    // 중복되지 않을때만 map에 원소와 그에 대응되는 순위를 넣어줌
    if(!rank.containsKey(k)) {
        rank.put(k, index);
        index++;
    }
}

StringBuilder sb = new StringBuilder();
for(int key : arr) {
    int ranking = rank.get(key);
    sb.append(ranking).append(' ');
}

HashMap자료구조로 키 = Integer, 값 = Integer를 사용할 것이다.

또한 copy배열은 입력받은 arr배열을 복제하여 정렬을 한 배열(>기본값 : 오름차순 정렬)이며,

기존 배열을 손상시키지 않는 방법으로 선택하였다.

rank는 해시맵인데, 복제된 배열에서 값을 하나씩 뽑아내어 그 값이 rank안에 포함되어있는지 여부를 검사하여

if) 포함되지 않는다면

rank에 (뽑은값, 인덱스) 순서로 저장한다. 그 후 인덱스는 증가시킨다.

>> rank의 구조 = {2=2, 4=3, -9=1, -10=0}
copy배열에서 오름차순 정렬로 해시맵 rank에 넣었지만 해시맵은 순서를 보장하지 않는 특성이 있으므로
이러한 구조를 가진다.

-10 = 0번인덱스
-9 = 1번인덱스
2 = 2번인덱스
4 = 3번인덱스

의 의미를 가진다.

이제 기존배열에서는 key를 뽑아내어

rank라는 해시맵에서 key를 기준으로 "값을 추출해낸다 = 인덱스"

인덱스마다 출력해보면
key = 2를 통해 뽑아낸 인덱스 값 = 2
key = 4를 통해 뽑아낸 인덱스 값 = 3
key = -10를 통해 뽑아낸 인덱스 값 = 0
key = 4를 통해 뽑아낸 인덱스 값 = 3
key = -9를 통해 뽑아낸 인덱스 값 = 1

그 인덱스 값을 StringBuilder 에 누적시켜 출력한다.

---

<전체코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		int[] copy = new int[N]; // 오름차순 정렬된 배열
		Map<Integer, Integer> rank = new HashMap<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			// 배열 2개에 동시에 값 넣기
            arr[i] = copy[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(copy);
		
		int index = 0;
		for(int k : copy) {
			// 중복되지 않을때만 map에 원소와 그에 대응되는 순위를 넣어줌
			if(!rank.containsKey(k)) {
				rank.put(k, index);
				index++;
			}
		}
		
		System.out.println("rank 맵 = " + rank);
		
		StringBuilder sb = new StringBuilder();
		for(int key : arr) {
			int ranking = rank.get(key);
			sb.append(ranking).append(' ');
		}
		System.out.println(sb);
	}
}

---

최빈값 구하는 문제와 유사하게 개수를 체크하고 그에 따라 압축되는 압축률이 결정되는 것 같은 점을 공부할 수 있었다.

특히나 HashMap구조를 이용하여 값의 개수를 체크하는 부분과 get으로 키를 넣으면 값을 가져오고,값을 넣으면 키를 가져오는 해시맵의 특징도 이해할 수 있었다.

 

---

문제링크)
https://www.acmicpc.net/problem/18870

18870번: 좌표 압축