[백준] 10816. 숫자 카드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

    static int getLeftIndex(int[] arr, int n) {
        int st = 0, en = arr.length;
        while (st < en) {
            int mid = (st + en) / 2;
            if (arr[mid] >= n) en = mid;
            else st = mid + 1;
        }
        return st;
    }

    static int getRightIndex(int[] arr, int n) {
        int st = 0, en = arr.length;
        while (st < en) {
            int mid = (st + en) / 2;
            if (arr[mid] <= n) st = mid + 1;
            else en = mid;
        }
        return st;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] num = new int[m];
        st = new StringTokenizer(br.readLine(), " ");
        for (int j = 0; j < m; j++) {
            num[j] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(cards);

        StringBuilder sb = new StringBuilder();
        for (int i : num) {
            sb.append(getRightIndex(cards, i) - getLeftIndex(cards, i)).append(' ');
        }

        System.out.println(sb);
        br.close();
    }
}

이분 탐색을 활용하여 중복 원소의 왼쪽 index, 오른쪽 index를 구해서 중복 횟수를 구할 수 있다.

i의 원소를 한 칸씩 뒤로 옮기고 i에 해당 원소를 삽입했을 때 오름차순 정렬이 유지되는 i를 기준으로 한다.

구간을 절반으로 잘 쪼갤 수 있도록 mid 값을 선택할 때 주의 해야한다.

st 와 en이 1차이날 때를 주의깊게 확인해보자.

무한루프에 빠지지 않도록 mid값이 적절히 바뀔 수 있도록 해야한다. ex) mid = (st+en+1)/2