[백준/BOJ] 18870번 : 좌표 압축 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

18870번: 좌표 압축

---

- 문제 -

 

난이도 실버 2 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

좌표 압축은 알고리즘의 하나라고 한다. 솔직히 이번 문제에서 처음 접했고, 그렇다보니 이런 알고리즘이 있다는 것도 처음 알았다. 그래서 이런 저런 정의를 봤지만 하나같이 같은 말들로 하나같이 이해가 가질 않았다.

우선 사람들이 말하는 좌표압축 알고리즘은 좌표의 끝과 끝의 범위가 매우 클 경우, 이름처럼 그 범위를 압축해서 범위를 줄이는 것이라고 한다. 이해가 안간다... 그리고 이번문제는 좌표 압축이 맞나 싶기도 하다. 물론 입력되는 값이 최소 -1000000000 ~ 1000000000 까지기 때문에 매우 큰 범위인 것은 맞다. 하지만 좌표 압축으로 구하는 방식과 같은지는 모르겠다.

 

필자가 이해한 좌표압축이 아닌 이번 문제는 주어진 값들의 순서를 0부터 매기는 거라고 이해했다.

예제 1로 보면 2 4 -10 4 -9이다. 순서를 0부터 매기니 작은 값부터 보자. 값들 중 제일 작은 값은 -10. 다음은 -9, 2, 4가 된다. 그렇다면 받은 값들 순서대로 각자의 순서를 출력하자. 2는 3번째이니 2, 4는 4번째이니 3, -10은 1번째이니 0, 4는 3, -9는 1. 그렇다면 출력값은 2 3 0 3 1이 되는 것이다.

 

풀이를 보자.

배열을 이용해, 입력값들을 정렬을 해준다.

HashMap에 정렬된 배열의 값들을 첫번째 값부터 key에는 배열에 저장 된 값을, value에는 순서를 저장해준다.

HashMap에 다 저장했으면, 처음에 입력한 값의 순서대로 HashMap에 저장된 값을 출력해준다.

 

코드를 보자.

---

-풀이-

 

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 IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		//처음에 입력받은 순서를 알기위한 배열
		int[] input = new int[N];
		//정렬하기위한 배열
		int[] Array = new int[N];
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++) {
			int num = Integer.parseInt(st.nextToken());
			input[i] = num;
			Array[i] = num;
		}
		
		//정렬
		Arrays.sort(Array);
		
		//첫번째값을 우선 저장한다.
		hash.put(Array[0], 0);
		//순서 변수
		int rank = 1;
		//인덱스 변수
		int index = 1;
		//인덱스가 N보다 작을때 반복한다.
		while(index < N) {
			//정렬했기 때문에 앞 뒤 값이 중복이 아닐때
			if(Array[index] != Array[index - 1]) {
				hash.put(Array[index], rank);
				rank++;
			}
			//중복이면 순서는 그대로, 인덱스만 +1을 해준다.
			index++;
		}
		
		for(int i = 0; i < N; i++) {
			sb.append(hash.get(input[i])).append(" ");
		}
		System.out.println(sb);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.