BOJ 10816 - 숫자 카드 2 / C++

문제 링크 : https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

 

풀이

이전의 숫자 카드 문제는 아래와 같이 풀이하였다.

https://appdevorsec.tistory.com/42

 

하지만, 숫자 카드 2는 시간 제한이 더 줄어들었으므로 이진 탐색을 통해 풀어야한다.

lower_bound는 찾으려는 값보다 같거나 큰 값이 존재하는 인덱스,

upper_bound는 찾으려는 값을 초과하는 첫 인덱스이다.

 

예를 들어, [1, 2, 3, 3, 3, 4, 5]라는 배열이 존재할때 3을 각각 lower_bound, upper_bound를 통해 찾으면

3보다 같거나 큰 숫자가 등장하는 인덱스는 2이므로 lower_bound: 2,

3을 초과하는 첫 인덱스는 5이므로 upper_bound: 5이다.

 

따라서, upper_bound - lower_bound를 해주면 찾고자하는 값이 몇 번 등장하는지 알 수 있다.

 

 

코드

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

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

    int n, m;
    vector<int> v;

    cin >> n;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    sort(v.begin(), v.end());

    cin >> m;
    for(int i=0; i<m; i++){
        int tmp;
        cin >> tmp;
        
        int cnt = upper_bound(v.begin(), v.end(), tmp) - lower_bound(v.begin(), v.end(), tmp);
        cout << cnt << ' ';
    }
}