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

 

 

 

🧫 문제 분석

 

✔️ 출처

좌표 압축 실버 2

 

📖 문제

 

이분탐색을 이용해서 주어진 좌표의 인덱스 위치를 빠르게 찾는 문제이다.

 

우선 문제를 이해하기 위해 좌표평면을 그린다.

 

Xi > Xj 를 만족하는 '서로 다른' Xj의 개수가 Xi를 압축한 좌표이다. 

예제 1번을 예로 정렬해보자

 

-10  -9     2    4(2개)

 

이제 첫 입력 좌표인 x1의 경우 2 > Xj의 개수를 찾으면 된다

여기서 2보다 작은건 -10, -9이므로 2개

즉, X1의 압축된 좌표는 2이다. 

 

이 문제에서 중요한 점은 중복값 처리이다. 

 

예제 2번에서 친절히 알려준다.

 

999 999 999 1000 1000 1000 

 

사실상 좌표평면에서는 999 1000 이 두개이다.

따라서 중복을 제거해야한다. 

 

배열에 중복을 제거한 좌표들을 정렬해서 넣고

 

xi의 값을 가진 인덱스를 이분탐색으로 찾는다. 그때 나온 인덱스가 바로 압축된 좌표이다. 

 

 

---

🔅 문제 풀이

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();
        TreeSet<Integer> set = new TreeSet<>();

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

        int[] origin = new int[n];

        // 원본 좌표와, 정렬된 좌표들 저장
        for (int i = 0; i < n; i++) {
            origin[i] = Integer.parseInt(st.nextToken());
            set.add(origin[i]);
        }

		// 정렬된 좌표들을 배열로 반환
        int[] coords = set.stream().mapToInt(Integer::intValue).toArray();


        for (int x : origin) {
            int front = 0, back = coords.length - 1;
            int compressedCoords = 0;

            while (front <= back) {

                int mid = (front + back) >>> 1;

                if (coords[mid] < x) {
                    front = mid + 1;
                } else {
                    compressedCoords = mid;
                    back = mid - 1;
                }
            }
            sb.append(compressedCoords).append(" ");
        }


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

 

 

 

❗ 오답노트 / 필요한 지식

1.  처음에는 우선순위 큐 + 해시 셋으로 했으나 생각해보니 트리셋을 쓰면 되서 TreeSet을 사용했다.