BOJ 10816 - 숫자 카드 2

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

첫번째로 소유하고 있는 카드를 입력받는다.

그 이후 입력받는 카드를 몇개 가지고 있는지 출력한다.

Solution

Binary Search 를 활용하여 lower bound와 upper bound를 사용하여 정답을 구할 수 있다.

• lower bound : 크거나 같은 수 중 첫번째 수

• upper bound : 큰 수 중 첫번째 수

1	3	3	4	5	5

3의 lower bound : 3 (index = [1])
3의 upper bound : 4

인덱스로 upper bound - lower bound 를 할 시 같은수의 개수가 나온다.
3(index of upper b) - 1(index of lower b) = 2

lower bound는 같은수가 있을때는 가장 첫번째 위치를 찾아야하므로 수를 찾은후에는 lower bound를 저장하고 right를 mid-1해준후에 탐색을 계속해준다.

upper bound는 값을 찾았을때 그보다 큰 값을 취해주어야하기 때문에 upper bound에 mid+1 , left또한 mid+1 한후에 탐색을 계속해준다.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    cin >> m;

    while (m--) {
        int goal;
        cin >> goal;

        int left = 0;
        int right = n - 1;
        int lb, ub;
        lb = 0;

        //lower bound
        while (left <= right) {
            int mid = (left + right) / 2;

            if (a[mid] == goal) {
                lb = mid;
                right = mid - 1;
            }

            else if (a[mid] > goal) {
                right = mid - 1;
            }

            else {
                left = mid + 1;
            }
        }

        left = 0;
        right = n - 1;
        ub = 0;

        //upper bound
        while (left <= right) {
            int mid = (left + right) / 2;

            if (a[mid] == goal) {
                ub = mid+1;
                left = mid + 1;
            }

            else if (a[mid] > goal) {
                right = mid - 1;
            }

            else {
                left = mid + 1;
            }
        }

        //같은수의 개수 = upper bound - lower bound
        cout << ub - lb << ' ';
    }

    return 0;
}

참고 : https://code.plus/course/43 , 분할 정복