[백준 18870] 좌표 압축 (JAVA)

백준 18870번 문제 - 좌표 압축 

18870번: 좌표 압축

---

문제 분석

 

• 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
• Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
  • 가장 작은 수를 0으로 해서 정렬에 따라 숫자가 1씩 증가한다.
  • 중복 수는 동일한 수를 준다.
  • ex) 2 4 -10 4 -9 → -10 -9 2 4 4 → -10:0 -9:1 2:2 4:3 4:3

---

해결 포인트

 

• 정렬하지 않는 배열, 정렬하는 배열 두가지 구현
• 정렬하는 배열 사용법
  • 첫번째, TreeSet으로 중복 처리 및 정렬한 후, List로 변환해서 indexOf로 해당 숫자 정렬 결과 알아내기 (인덱스 = 압축 결과)
    - 실패 (List 변환에서 컴파일 에러 : Java 11에서는 toList() 메서드가 List 인터페이스에서 직접 제공되지 않는다.)
  • 두번째, ArrayList를 Collections.sort 한 후, indexOf로 해당 숫자 정렬 결과 알아내기
    - 실패 (indexOf 가 생각보다 시간이 오래 소요, 시간 초과)
  • 세번째, ArrayList 중복 제거는 stream().distinct().toArray()로 해결. 이진탐색으로 해당 숫자 정렬 결과 알아내기
    - 성공 ! 

---

코드

 

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

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

        int [] nums = new int[N];
        int [] sort = new int[N];

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

        sort = Arrays.stream(sort).distinct().toArray();
        Arrays.sort(sort);

        for (int i = 0; i < N; i++) {
            bw.write(binary(sort, nums[i], 0, sort.length) + " ");
        }

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

    public static int binary(int [] sort, int value, int start, int end) {
        int index = (start + end)/2;
        if(sort[index] == value) return index;
        if(sort[index] > value)
            return binary(sort, value, start, index-1);
        return binary(sort, value, index+1, end);
    }
}