[백준][Java] 18870번 : 좌표 압축

[문제 링크]

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

---

문제 설명

• 수직 선 위의 N개 좌표에 대해서 좌표 압축을 적용해서 출력
• Xi 를 좌표 압축한 결과 X'i는 Xi > Xj를 만족하는 Xj 의 개수(Xj는 모두 서로 다른 좌표이다)
• 입력: N(좌표개수), N개의 좌표(X1, X2, ..., XN)
• 출력: 좌표압축을 적용한 결과(X'1, X'2, ..., X'N)
• ex1) 2  4  -10  4  -9 의 좌표값이 주어졌을 때, 좌표압축한 결과는 2 3  0  2  1  이다.
           2 보다 작은 값은 -10  -9,
           4 보다 작은 값은 -10  -9  2,
          -10 보다 작은 값은 없고,
          -9 보다 작은 값은 -10
• ex2) 1000  999  1000  999  1000  999 의 좌표값이 주어졌을 때, 좌표압축한 결과는 1  0  1  0  1  0  이다.

 

 

 

문제 풀이

주어진 숫자들을 서로 비교하여 자기 자신보다 작은 수의 개수를 구하는 문제 라고 이해하고 문제를 풀었다.

 

실패한 풀이 : 시간초과

• 단순 반복문으로 count했더니 중복을 해결하지 못하고 실패했다.
• 이 코드로 ex2) 를 실행하며 3  0  3  0  3  0 값이 출력된다.

import java.io.*;
import java.util.StringTokenizer;

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));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (array[i] > array[j]) {
                    count++;
                }
            }
            sb.append(count + " ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

 

 

 

성공한 풀이 : HashMap 사용

• HashMap을 사용해서 각 원소값에 대한 '순위'를 매긴다.
• 작은 값이 높은 순위를 갖고, 중복되는 원소는 같은 순위를 가진다.

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] array = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        int[] array_sort = array.clone();
        Arrays.sort(array_sort);

        HashMap<Integer, Integer> map = new HashMap<>();
        int rank = 0;
        //정렬된 배열을 돌면서 순위를 매긴다.
        for (int i : array_sort) {
            if (!map.containsKey(i)) {
                map.put(i, rank);
                rank++;
            }
        }

        //원본배열을 돌면서 해당 원소(key)의 value 값을 출력한다.
        for (int i : array) {
            bw.write(map.get(i) + " ");
        }

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

 

 

🔶입력받은 배열 복제 & 정렬

입력받은 배열을 복제하고, 이 배열을 오름차순 정렬한다.

(원본배열은 나중에 결과를 출력할 때 사용된다.)

int[] array_sort = array.clone();
Arrays.sort(array_sort);

 

 

🔶 Hashmap을 이용하여 count 하기

정렬된 배열(array_sort)를 for문으로 돌면서 map에 원소와 순위값을 추가한다.

이 때, map에 동일한 원소가 있지 않을 경우에만 값을 추가하여 중복 원소를 해결한다.

 

ex1) 를 예를 들어 설명해보면 정렬된 배열은 -10  -9  2  4  4  이다. for문을 실행하면,

key = -10, value = 0 값이 들어가고, rank = 1 로 변경

key = -9, value = 1 값이 들어가고, rank = 2 로 변경

key = 2, value = 2 값이 들어가고, rank = 3 로 변경

key = 4, value = 3 값이 들어가고, rank = 4로 변경

마지막 4는 map이 이미 동일한 key값이 존재하기 때문에, map에 추가되지 않는다.

따라서 map에는 (key : value) → (-10, 0), (-9, 1), (2, 2), (4, 3) 값이 들어있다.

 

for (int i : array_sort) {
    if (!map.containsKey(i)) {
        map.put(i, rank);
        rank++;
    }
}

 

 

🔶 결과 출력

입력받은 순서대로 좌표압축한 값을 출력해야한다. 

따라서 원본배열인 array를 for문으로 돌면서 map에서 해당 key에 있는 value 를 가져온다.

for (int i : array) {
            bw.write(map.get(i) + " ");
}

 

 

 

 

✔️ 좌표압축

수의 범위가 크게 주어질 때, 인덱스를 이용하여 범위를 줄이는 기법

 

---

[참고]

https://st-lab.tistory.com/279

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