[백준] 좌표 압축 JAVA

반응형

728x90

[백준] 좌표 압축 - SILVER II 18870번

---

접근

• 정렬 & Map

---

풀이

백준 실버 2 난이도의 좌표 압축 문제로 입력받은 좌표를 기준에 따라 압축하여 출력하는 문제이다. 좌표 압축이 무엇을 뜻하는지 어떤 동작을 하라는 건지 잘 모른다면 설명만 보고 이해가 조금 힘들 수 있다.

 

문제 자체는 굉장히 간단한 문제로 입력받은 좌표값을 순서대로 하나씩 압축하면 되는 것으로 압축 방법은 그냥 압축할 좌표보다 작은 값의 좌표가 몇 개인지 구하기만 하면 끝이다. 아래 예제 1번의 예시를 보면 바로 이해할 수 있을 것이다.

예제 1번 
좌표 배열 : [2 4 -10 4 -9]

순서대로 압축 시작
i = 0, arr[0] =   2 -> 배열 내   2 보다 작은 값 -10, -9    -> 압축 결과 2
i = 1, arr[1] =   4 -> 배열 내   4 보다 작은 값 -10, -9, 2 -> 압축 결과 3
i = 2, arr[2] = -10 -> 배열 내 -10 보다 작은 값  X         -> 압축 결과 0
i = 3, arr[3] =   4 -> 배열 내   4 보다 작은 값 -10, -9, 2 -> 압축 결과 3
i = 4, arr[4] =  -9 -> 배열 내  -9 보다 작은 값 -10        -> 압축 결과 1

최종 결과
[2, 3, 0, 3, 1]

진짜 단순하게 압축할 값 보다 작은, 미만의 값을 가진 좌표 개수가 압축 값이 된다.

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] xArray = br.readLine().split(" ");

        int[] sortedXArray = Arrays.stream(xArray).mapToInt(Integer::parseInt).sorted().distinct().toArray();
        Map<Integer, Integer> countMap = new HashMap<>();

N의 최대 범위가 1,000,000 이고 좌표를 압축할 때마다 출력해 주기 위해 BufferedWriter를 사용해 출력해 주었다. 입력받은 배열을 stream을 통해 변환해 주었는데 정렬과 중복 제거를 같이 해주었다. 이번 압축은 Map에 인덱스 값을 넣어 진행해 주었다.

	for (int i = 0; i < sortedXArray.length; i++) {
            int x = sortedXArray[i];

            countMap.put(x, i);            
        }

중복 제거와 정렬이 완료된 배열을 순회하며 맵에 값을 넣어주는 과정이다. 이 과정을 통해 Map에 key값으로 사용되는 좌표 값보다 작은 원소의 개수가 몇 개인지 저장된다. 정렬이 된 배열을 순회하기 때문에 인덱스의 값이 해당 좌표보다 작은 원소의 개수와 동일하다.

	for (String x : xArray) {
            int value = countMap.get(Integer.parseInt(x));

            bw.write(value + " ");
        }

Map에 값을 다 집어넣었다면 정렬이 안된 원본 배열을 순회하며 Map에서 값을 꺼내오기만 하면 압축한 값이 된다.

---

전체 코드

import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String[] xArray = br.readLine().split(" ");

        int[] sortedXArray = Arrays.stream(xArray).mapToInt(Integer::parseInt).sorted().distinct().toArray();
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int i = 0; i < sortedXArray.length; i++) {
            int x = sortedXArray[i];

            countMap.put(x, i);
        }


        for (String x : xArray) {
            int value = countMap.get(Integer.parseInt(x));

            bw.write(value + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}