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

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

 

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

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

---

1.  아이디어

 

수직선 위에 주어진 좌표가 전체 좌표 중 중복을 제외하고 몇 번째로 큰 좌표인지 구하는 문제로 좌표에 대한 정렬을 수행 후 Map을 활용하는 방식과 이분 탐색을 활용하는 방식 두가지로 구현할 수 있었다.

---

2. 문제풀이

 

1. HashMap

주어진 좌표를 List로 받은 후 TreeSet에 복사해서 중복 제거 + 정렬을 수행했다. 이후 TreeSet을 순회하며 HashMap에 좌표와 순서를 저장해주었고 List를 순회하며 HashMap에서 순서를 조회하는 방식으로 구현했다.

 

2. 이분 탐색

주어진 좌표를 배열로 받은 후 HashSet에 넣어 중복 제거를 수행했다. 이후 HashSet과 같은 크기의 배열에 넣고 정렬을 수행한 후 좌표를 받았던 배열을 순회하며 이분 탐색으로 순서를 조회하는 방식으로 구현했다.

---

3. 코드

 

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

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        List<Integer> list = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        Set<Integer> set = new TreeSet<>(list);
        Map<Integer, Integer> map = new HashMap<>();
        int order = 0;
        for (int n : set) {
            map.put(n, order++);
        }

        for (int n : list) {
            sb.append(map.get(n)).append(" ");
        }

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

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

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

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

        Set<Integer> set = new HashSet<>();
        for (int n : arr) {
            set.add(n);
        }

        int[] sortedArr = new int[set.size()];
        int idx = 0;
        for (int n : set) {
            sortedArr[idx++] = n;
        }
        Arrays.sort(sortedArr);

        for (int i = 0; i < N; i++) {
            sb.append(binarySearch(sortedArr, arr[i])).append(" ");
        }

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

    private static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] < target) left = mid + 1;
            else if (arr[mid] > target) right = mid - 1;
            else return mid;
        }

        return -1;
    }

}

---

4. 후기

 

- HashMap

- 이분 탐색