Baekjoon 10816 (숫자 카드 2)

Baekjoon 10816, 백준 10816 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <algorithm>
using namespace std;

int N, M;

int Upper_Bound(int* arr, int target) {
    int upper_bound = -1;
    int left = 0, right = N-1;
    while(left <= right) {
        int middle = (left + right) / 2;
        if(arr[middle] > target) {
            right = middle - 1;
            continue;
        }
        else if(arr[middle] < target) {
            left = middle + 1;
            continue;
        }
        else if(arr[middle] == target) {
            upper_bound = middle;
            left = middle + 1;
            continue;
        }
    }
    return upper_bound;
}

int Lower_Bound(int* arr, int target) {
    int lower_bound = -1;
    int left = 0, right = N-1;
    while(left <= right) {
        int middle = (left + right) / 2;
        if(arr[middle] > target) {
            right = middle - 1;
            continue;
        }
        else if(arr[middle] < target) {
            left = middle + 1;
            continue;
        }
        else if(arr[middle] == target) {
            lower_bound = middle;
            right = middle - 1;
            continue;
        }
    }
    return lower_bound;
}

int main() {
    // get inputs
    scanf("%d",&N);
    int* arr = new int[N];
    for(int i = 0; i < N; i++){
        scanf("%d",&arr[i]);
    }
    scanf("%d",&M);
    int* brr = new int[M];
    for(int i = 0; i < M; i++){
        scanf("%d",&brr[i]);
    }

    // sort array
    sort(arr, arr+N);

    // Binary Search
    for(int i = 0; i < M; i++){
        int upper = Upper_Bound(arr, brr[i]);
        int lower = Lower_Bound(arr, brr[i]);
        if(upper == -1) printf("0 ");   // brr[i] doesn't exist in arr
        else printf("%d ", upper - lower + 1);
    }

    delete[] arr;
    delete[] brr;
}

이분 탐색을 응용하는 문제!
특정 숫자의 개수를 확인하는 방법이다.

정렬을 한 후, 그 숫자 중 가장 작은 index(lower_bound)와 큰 index(upper_bound)를 구하여
upper_bound - lower_bound + 1 로 개수를 구하는 아이디어.