[백준] 18870번 : 좌표 압축 - JAVA [자바]

 

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

18870번: 좌표 압축

 

 

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

이 번엔 단계별 풀이가 아닌 다른 문제를 한 번 풀어보려 한다.

 

알고보니 정렬 파트에 추가된 문제였다..

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

위 문제를 보니 좌표 압축이라고는 되어있긴 하지만, 정확히는 좌표 압축 알고리즘을 활용한 ranking list를 만드는 문제라고 보는 것이 좀 더 직관적이지 않나.. 생각을 한다.

 

여튼, 위와 같은 문제 부류를 coordinate Compression(좌표 압축)이라고 하는데, 어떤 특정한 알고리즘이 존재하는게 아니라, 하나의 카테고리라고 보면 된다. 1차원 데이터의 경우는 위 문제처럼 순위를 매기거나 하는 문제들을 쓸 때 접하게 되고, 대부분은 2차원 이상의 좌표에서 데이터 압축을 해야 할 경우에 접하게 되는 경우가 많다.

 

특히 데이터의 범위가 매우 크거나, 단순화 해야 할 일들이 있을 때 많이 쓰이게 되는데, 대표적인 예시로 GPS 좌표 압축같이 2차원 혹은 3차원 데이터를 그리드로 놓고 보았을 때 데이터 값들을 단순화하여 압축하거나(손실 압축) 특정 공식에 의해 무손실 압축을 하는 등 데이터의 양을 압축시키는 방식 등이 있다.

 

 

쉬운 예시로 다음과 같다.

 

2차원 그리드에서 특정 좌표에서 가장 멀리 갈 수 있는 최단 거리 좌표를 구하고자 한다. 이 때 장애물은 빨간색 블럭으로 해당 블럭을 넘어다닐 수 없다고 한다.

 

알고리즘을 좀 풀어보셨다면 위와 같은 문제는 보통 BFS 로 풀 것이다. 그런데 그 좌표가 어마어마하게 많다면?

이러한 문제를 풀 때 다음과 같이 좌표를 압축 할 수 있다.

 

 

 

보면 각 블럭(좌표)을 새로운 그리드로 각 선분의 정점만 좌표로 두고 나머지 불필요한 좌표는 모두 지웠다.

오른쪽 그림처럼 압축을 한 뒤, BFS로 탐색을 하고, 탐색 된 블럭에서 원본에서 압축 된 블럭 간격을 측정하여 거리를 계산할 수 있다.

 

그러면 탐색해야 할 좌표가 매우 적어짐을 확인 할 수 있다.

 

 

위와 같이 불필요한 좌표를 날려 단순화 하는 방식도 있고, 데이터 자체를 압축 하는 방식도 존재한다. 이러한 부류는 여러분이 많이 접하는 ZIP 파일 같은 곳에도 쓰이기도 한다.

 

 

 

 

문제 유형에 대한 설명은 이쯤으로 하고, 문제를 본격적으로 풀어보자.

 

 

이 문제를 아주아주 쉽게 해석하자면, 배열의 각 원소값에 대한 '순위'를 매기는 것이다.

문제 예시를 예로들어 보자면, 다음과 같이 입력이 주어졌다.

 

arr = {2, 4, -10, 4, -9}

 

여기서 각 원소를 순위를 매기자는 것이다. (낮은 값이 순위가 높다는 점을 유의하자)

가장 낮은 값인 -10이 0순위가 될 것이다. 그 다음 -9가 1순위 .. 이런식으로 말이다.

 

즉, rank로 보면 다음과 같다.

 

rank = {2, 3, 0, 3, 1}

 

 

 

그러면 문제를 어떻게 접근하는 것이 좋을까? 위 문제를 자세히 살펴보면 다음과 같이 두 가지 조건이 있다는 것을 볼 수 있다.

 

1. 낮은 값이 높은 순위를 갖는다. (가장 높은 순위는 0순위다.)

2. 중복되는 원소는 같은 순위를 갖는다.

 

자, 한 번 하나의 조건씩 구체적으로 살펴보자.

 

낮은 값이 높은 순위를 갖는다는 것, 결국 순위를 정한다는 것은 오름차순으로 '정렬'을 했을 때 첫 번째 인덱스에 있는 원소가 가장 높은 순위를 갖고, 반대로 가장 마지막에 있는 원소가 가장 낮은 순위를 갖는다는 것을 의미한다. 즉, 우리는 정렬을 떠올려야 한다.

 

다음으로 중복되는 원소는 같은 순위를 갖는다는 것은 앞선 예제에서도 보았듯이 4라는 값에 대응되는 순위는 모두 3으로 같은 순위로 매칭이 되어야 한다는 것이다.

이 부분은 무엇을 활용 할 수 있을까? 중복되는 원소를 하나만 갖고 있을 수 있도록 하는 자료구조인 Set 혹은 Map 자료구조를 활용하면 되지 않을까?

 

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

 

 

알고리즘 과정은 매우 단순하다. 글 보다는 이미지가 훨씬 이해하기 편할테니, 한 번 아래 과정을 보도록 하자.

 

 

 

위 과정을 그대로 코드로 옮기면 된다.

 

간단하게 부분적으로만 코드로 작성해보자.

 

int[] origin = new int[N];	// 원본 배열
int[] sorted = new int[N];	// 정렬 할 배열
HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();	// rank를 매길 HashMap

// 정렬 할 배열에 대해 정렬을 수행해준다.
sort(sorted);
		
		
// 정렬 된 배열을 순회하면서 map에 넣어준다.
int rank = 0;
for(int v : sorted) {
	/*
	 *  이 때 만약 앞선 원소가 이미 순위가 매겨졌다면
	 *  중복되면 안되므로, 원소가 중복되지 않을 때만
	 *  map에 원소와 그에 대응되는 순위를 넣어준다.
	 */
	if(!rankingMap.containsKey(v)) {
		rankingMap.put(v, rank);
		rank++;		// map에 넣고나면 다음 순위를 가리킬 수 있도록 1을 더해준다.
	}
}
		
// 원본 배열을 차례대로 순회하면서 해당 원소에 대한 rank를 갖고온다.
for(int key : origin) {
	print(rankingMap.get(key));	// 원본 배열 원소(key)에 대한 value(rank)를 갖고온다.
}

 

위와 같이 해주면 된다.

 

 

이 때 주의해야 할 부분은 map에 원소를 넣을 때, 무작정 넣는 것이 아닌, 반드시 map에 똑같은 원소가 들어있지 않을 경우에만 원소와 rank값을 넣어주어야 한다. 이 부분만 조심해주면 그리 어렵지 않게 풀이할 수 있다.

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다. 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 2가지 입력 방법을 통해 성능을 비교해보려 한다. 필자가 미리 제출을 해보니, BufferedReader + StringBuilder로 풀이하더라도 시간이 많이 소요되는 문제였다. 그래서 이번에는 출력은 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.

 

1. Scanner + StringBuilder

2. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + StringBuilder]

 

import java.util.Scanner;
import java.util.HashMap;
import java.util.Arrays;


public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		int[] origin = new int[N];	// 원본 배열
		int[] sorted = new int[N];	// 정렬 할 배열
		HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();	// rank를 매길 HashMap

		
		for(int i = 0; i < N; i++) {
			// 정렬할 배열과 원본 배열에 값을 넣어준다.
			sorted[i] = origin[i] = in.nextInt();
		}
		
		// 정렬 할 배열에 대해 정렬을 수행해준다.
		Arrays.sort(sorted);
		
		
		// 정렬 된 배열을 순회하면서 map에 넣어준다.
		int rank = 0;
		for(int v : sorted) {
			/*
			 *  이 때 만약 앞선 원소가 이미 순위가 매겨졌다면
			 *  중복되면 안되므로, 원소가 중복되지 않을 때만
			 *  map에 원소와 그에 대응되는 순위를 넣어준다.
			 */
			if(!rankingMap.containsKey(v)) {
				rankingMap.put(v, rank);
				rank++;		// map에 넣고나면 다음 순위를 가리킬 수 있도록 1을 더해준다.
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int key : origin) {
			int ranking = rankingMap.get(key);	// 원본 배열 원소(key)에 대한 value(순위)를 갖고온다.
			sb.append(ranking).append(' ');
		}
		
		System.out.println(sb);
		
		

	}
}

 

 

 

 

 

---

- 방법 2 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 두 번째 라인을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Arrays;


public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] origin = new int[N];	// 원본 배열
		int[] sorted = new int[N];	// 정렬 할 배열
		HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();	// rank를 매길 HashMap

		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			// 정렬할 배열과 원본 배열에 값을 넣어준다.
			sorted[i] = origin[i] = Integer.parseInt(st.nextToken());
		}
		
		// 정렬 할 배열에 대해 정렬을 수행해준다.
		Arrays.sort(sorted);
		
		
		// 정렬 된 배열을 순회하면서 map에 넣어준다.
		int rank = 0;
		for(int v : sorted) {
			/*
			 *  이 때 만약 앞선 원소가 이미 순위가 매겨졌다면
			 *  중복되면 안되므로, 원소가 중복되지 않을 때만
			 *  map에 원소와 그에 대응되는 순위를 넣어준다.
			 */
			if(!rankingMap.containsKey(v)) {
				rankingMap.put(v, rank);
				rank++;		// map에 넣고나면 다음 순위를 가리킬 수 있도록 1을 더해준다.
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int key : origin) {
			int ranking = rankingMap.get(key);	// 원본 배열 원소(key)에 대한 value(순위)를 갖고온다.
			sb.append(ranking).append(' ');
		}
		
		System.out.println(sb);
		
		

	}
}

 

 

 

알고리즘 자체는 그리 어려운 문제는 아니였을 것이다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 36233890  -  방법 2 : BufferedReader + StringBuilder

채점 번호 : 36233883  -  방법 1 : Scanner + StringBuilder

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 번 문제는 이후 여러분이 압축 관련 알고리즘을 풀이하는데 도움이 될 것이다. 물론 정렬파트에 있긴 하지만 좌표압축 개념은 세그먼트 트리 부분에서 은근 자주 쓰이기 때문에 위와 같은 개념을 응용하여 확장 할 수 있다.

 

 

여담으로 이 번 문제에 시간이 많이 걸리는 TC가 있어 시간초과를 받는 경우도 있을 수 있다고 본다.  만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.