백준 10816 자바 - 숫자 카드 2

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

10816번: 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

코드

import java.io.*;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] arr = br.readLine().split(" ");
        int[] sgList = new int[n];
        for (int i = 0; i < n; i++) {
            sgList[i] = Integer.parseInt(arr[i]);
        }
        Arrays.sort(sgList);
        int m = Integer.parseInt(br.readLine());
        List<Integer> cdList = Arrays.asList(br.readLine().split(" ")).stream().map(Integer::parseInt).collect(Collectors.toList());

        cdList.stream().forEach(i -> sb.append(upperBound(sgList, i) - lowerBound(sgList, i)).append(" "));

        bw.write(sb.toString());

        bw.flush();
        br.close();
        bw.close();

    }

    private static int lowerBound(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = (low + high) / 2;
            if (target <= arr[mid]) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
    private static int upperBound(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = (low + high) / 2;
            if (target < arr[mid]) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }

}

풀이

 정렬된 배열에서 가장 첫번째 일치하는 원소의 인덱스를 가장 마지막 일치하는 원소의 인덱스에서 빼주면, 해당 원소의 개수를 구할 수 있다.