백준 10816 - 숫자 카드 2

1. 문제 정리
  - n개의 숫자 카드가 주어진다.

  - m개의 정수가 주어진다. 

  - 각 정수는 -10000000 이상, 10000000 이하에 속한다.

  - m개의 수에 대하여 각 정수값이 n개의 숫자 카드에 몇개씩 있는지 출력한다.

2. 접근
  - n개의 숫자 배열에 대해 m개의 정수 중 하나를 target으로 이분탐색을 시행한다.

  - 이분탐색을 upperBound와 lowerBound 두개로 나누어 진행하고, 각 반환값의 차를 출력하여 배열에 포함된 값의 수를 찾는다.
 
3. 풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n, m;
vector<long long> a;
vector<long long> b;
int lo, hi;

int lowerBound(long long target){
    lo = 0;
    hi = n;
    while(lo < hi){
        int mid = (lo + hi) / 2;
        if(a[mid] < target) lo = mid+1;
        else if(a[mid] >= target) hi = mid;
    }
    return lo;
}

int upperBound(long long target){
    lo = 0;
    hi = n;
    while(lo < hi){
        int mid = (lo + hi) / 2;
        if(a[mid] <= target) lo = mid+1;
        else if(a[mid] > target) hi = mid;
    }
    return lo;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        long long input;
        cin >> input;
        a.push_back(input);
    }
    cin >> m;
    for(int i = 0; i < m; i++){
        long long input;
        cin >> input;
        b.push_back(input);
    }
    
    sort(a.begin(), a.end());
    cout << '\n';
    for(long long i: b){
        cout << upperBound(i) - lowerBound(i) << ' ';
    }
}

  - vector<long long> a, b : a는 n개의 정수, b는 m개의 정수를 담을 벡터이다.

  - int lowerBound(int target) : lowerBound 이분탐색을 실행하여 a배열에서 target이 등장하는 가장 작은 인덱스를 반환한다.

  - int upperBound(int target) : upperBound 이분탐색을 실행하여 b배열에서 target이 등장하는 가장 큰 인덱스 + 1을 반환한다.
 
4. 소감

  - 이분탐색을 시작한지 2일이 되었다. 아직 이분탐색이 어색한 감도 있지만, 특히 lowerBound와 upperBound가 아직은 낯설게 느껴진다. 그런 참에 이 문제는 나의 현 상황에 정말 잘 맞는 문제였다. 덕분에 lowerBound와 upperBound의 로직도 코드로 좀 더 이해할 수 있었다.