[BOJ/10816번숫자카드2] c++ / binary search

문제

주어진 카드의 개수를 출력하는 문제

 

문제풀이

1.주어진 카드를 정렬시킴

2.lower_idx에서 target이 들어갈 수 있는 왼쪽 인덱스 값을 구함

-if ( arr[mid] >= target ) en = mid; | arr[mid] = target과 같은 경우

3.upper_idx에서 target이 들어갈 수 있는 오른쪽 인덱스 값을 구함

-if ( arr[mid] <= target ) st = mid+1; | arr[mid] = target과 같은 경우

4.lower_idx - upper_idx 출력

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, t;
int arr[500005];
int lower_idx(int len, int target) {
    int st = 0;
    int en = len;
    while( st < en ) {
        int mid = ( st + en ) / 2;
        if ( arr[mid] >= target )
            en = mid;
        else 
            st = mid + 1;
    }
    return st;
}
int upper_idx(int len, int target) {
    int st = 0;
    int en = len;
    while( st < en ) {
        int mid = ( st + en ) / 2;
        if ( arr[mid] > target )
            en = mid;
        else 
            st = mid + 1;
    }
    return st;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for ( int i = 0; i < N; i++ ) cin >> arr[i];
    sort(arr, arr+N);

    cin >> M;
    while(M--) {
        cin >> t;
        cout << upper_idx(N, t) - lower_idx(N, t) << ' ';
    }
}

 

> upper_bound / lower_bound 사용

위의 upper_idx와 lower_idx의 기능과 동일

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, t;
int arr[500005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for ( int i = 0; i < N; i++ ) cin >> arr[i];
    sort(arr, arr+N);

    cin >> M;
    while(M--) {
        cin >> t;
        cout << upper_bound(arr, arr+N, t) - lower_bound(arr, arr+N, t) << ' ';
    }
}