[백준] 10816 숫자 카드 2 자바(Java)

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

중복된 값을 가지고 있는 배열에서 입력된 값이 몇 개 있는지 출력하는 문제

HashMap을 사용해서 풀 수 있지만 카테고리가 이분 탐색이라 이분탐색으로 문제 접근

1. 처음 입력받은 배열을 정렬
2. 입력 값 이분 탐색
   1. 동일 값 처음 인덱스
   2. 마지막 인덱스 구하기
3. 마지막 인덱스 - 처음 인덱스

동일 값 처음 인덱스

private static int lower(int[] arr, int key) {
    int si = 0;
    int li = arr.length;

    while (si < li) {
        int mid = (si + li) / 2;

        // 입력 값과 같거나 큰 값
        if (key <= arr[mid]) {
            li = mid;
        } else {
            si = mid + 1;
        }
    }
    return si;
}

동일 값 마지막 인덱스 구하기

    private static int uppend(int[] arr, int key) {
        int si = 0;
        int li = arr.length;

        while (si < li) {
            int mid = (si + li) / 2;

			// 입력 값보다 큰 값
            if (key < arr[mid]) {
                li = mid;
            } else {
                si = mid + 1;
            }
        }
        return si;
    }

전체 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int A = Integer.parseInt(st.nextToken());

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

        Arrays.sort(arr);

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < B; i++) {
            int key = Integer.parseInt(st.nextToken());
            sb.append(uppend(arr, key) - lower(arr, key)).append(" ");
        }

        System.out.println(sb);
    }

    private static int uppend(int[] arr, int key) {
        int si = 0;
        int li = arr.length;

        while (si < li) {
            int mid = (si + li) / 2;

            if (key < arr[mid]) {
                li = mid;
            } else {
                si = mid + 1;
            }
        }
        return si;
    }

    private static int lower(int[] arr, int key) {
        int si = 0;
        int li = arr.length;

        while (si < li) {
            int mid = (si + li) / 2;

            if (key <= arr[mid]) {
                li = mid;
            } else {
                si = mid + 1;
            }
        }
        return si;
    }
}