[Java] 백준 10816 : 숫자 카드 2(이진 탐색 구현)

이전에 학습한 이진 탐색을 구현해 보았다

이진 탐색을 하여 단 하나만 찾는 값을 찾는 것이 아닌 원하는 값의 갯수를 찾아야해서 살짝의 변화를 주었다

처음 등장하기 직전 위치를 찾는 lowerBound()와 마지막에 등장하는 위치의 upperBound()를 구성했다

array = [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]
위와 같이 정렬된 배열이 있고 10의 갯수를 알고싶다고 가정하자

아래는 시작 위치를 찾는 함수 이다

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

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

해당 함수를 따라가 보면
low = 0, high = 10
while(true)
mid = 5 => 6
if(false)
low = 6

while(true)
low = 6, high = 10
mid = 8 => 10
if(true)
high = 8

while(true)
low = 6, high = 8
mid = 7 => 10
if(true)
high = 7

while(true)
low = 6, high = 7
mid = 6
if(false)
low = 7

while(false)
return low
이 과정을 거쳐 10의 시작점은 7번째인 것을 알 수 있다

다음은 찾는 값의 마지막 위치를 찾는 upperBound이다

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

똑같이 과정을 살펴보면
low = 0, high = 10
while(true)
mid = 5 => 6
if(false)
low = 6

low = 6, high = 10
while(true)
mid = 8 => 10
if(false)
low = 9

low = 9, high = 10
while(true)
mid = 9 => 10
if(false)
low = 10

while(false)
return low

이 과정을 거쳐 마지막 위치는 10번째인걸 알 수 있다
그래서 출력을 upper - lower 를 하게되면 3이되어 10이 총 3개인 것을 알 수있따

전체 코드

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[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            int lowerBound = lowerBound(arr, target);
            int upperBound = upperBound(arr, target);
            bw.write((upperBound - lowerBound) + " ");
        }

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

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

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

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

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