백준 18870 좌표 압축 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/18870

풀이는 다음과 같다.

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

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

        //배열 주어지고, index 잡고, 해당 index의 숫자보다, 더 작은 수가 배열에 몇개 있는지.
        //이분탐색 로어바운드 찾기. 단순히 정렬하고 index를 출력하면 안된다.

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> a = new ArrayList<>(); //이건 받아놓고 중복 제거해줄 어레이리스트
        int[] arr = new int[N];

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

        List<Integer> a1 = a.stream().distinct().collect(Collectors.toList()); //중복제거
        Collections.sort(a1); //정렬






        for(int i = 0 ; i < N ; i++) { //처음 주어진 입력값 배열 (arr[i] 하나하나씩 이분탐색 lowerbound찾기)
            int s = 0;
            int e = a1.size()-1;

            while(s < e) {
                int m = (s+e)/2;

                if(a1.get(m) >= arr[i]) e = m;
                else s = m+1;
            }

            bw.write(String.valueOf(e) + " ");
        }

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

}

이분탐색을 모르신다면?https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

이분탐색 로직을 안다는 가정 하에 다른 부분을 설명하자면,
배열이
1000 999 1000 999 1000 999 일때,
1 0 1 0 1 0 을 출력해야 한다.

즉 같은 값은 제거해주고,
오직
999 1000 만 남고 해당 값의 lower bound를 찾으면 된다는 소리이다.

음.. 무슨말인지 모르겠는걸! 싶으면, 아래의 로직을 보면 이해할 수 있다.




배열 압축은 에서 수행했다. (중복 제거 스트림)

List<Integer> a1 = a.stream().distinct().collect(Collectors.toList()); //중복제거

그다음 정렬했다.

 Collections.sort(a1); //오름차순 정렬

그다음, 원래 입력값 arr 배열을 순회하며,
각각 arr[i] 값의 lowerbound를 a1배열 (정렬 + 중복제거) 에서 찾아주었다.

예를 들어
1000 999 1000 999 1000 999 = arr 이라면
999 1000 = a1 이 되고,

arr[i]값은 차례로
1000
999
1000
999
1000
999 가 된다.

그럼 a1에서 위의 차례대로 lowerbound를 찾게되니,

999 1000 (a1) 에서 1000의 lowerbound -> 1
999 1000 (a1) 에서 999의 lowerbound -> 0
999 1000 (a1) 에서 1000의 lowerbound -> 1
999 1000 (a1) 에서 999의 lowerbound -> 0
999 1000 (a1) 에서 1000의 lowerbound -> 1
999 1000 (a1) 에서 999의 lowerbound -> 0

을 차례대로 출력해주면 되는것이다.
해당 내용이 아래의 코드이다.

for(int i = 0 ; i < N ; i++) { //처음 주어진 입력값 배열 (arr[i] 하나하나씩 이분탐색 lowerbound찾기)
            int s = 0;
            int e = a1.size()-1;

            while(s < e) {
                int m = (s+e)/2;

                if(a1.get(m) >= arr[i]) e = m;
                else s = m+1;
            }

            bw.write(String.valueOf(e) + " ");
        }

간단한 이분탐색 문제이다.

이분탐색 구현을 외워놓자.

		int s = 0;
        int e = 끝의 길이;

        while(s < e) {
            int m = (s+e)/2;

            if(arr[m] >= lowerbound를 찾길 원하는 값) e = m;
            else s = m+1;
        }
        
        여기서, whlie문을 빠져나오면 e값이 lowerbound가 된다.