백준 10816번 C++ 풀이

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

10816번: 숫자 카드 2

https://codejin.tistory.com/128

백준 10815번 C++ 풀이

저번 숫자카드 문제는 이진탐색으로 카드가 있는지 없는지만 찾아야 했지만, 이번에는 개수까지 구해야 하는 문제.

 

STL의 count함수는 O(n)이기 때문에, 처음에는 이것으로 접근했다가 시간초과로 틀렸다. 결국 숫자카드 문제의 확장인 만큼 이진탐색으로 찾아야 하는 셈이다.

 

STL에는 binary_search함수는 bool이기 때문에 있는지 없는지만 판단한다면, 이진 탐색을 통해 구현된 lower_bound와 upper_bound함수는 각각 입력받은 범위에서 입력받은 요소의 이상, 초과하는 값이 처음 나오는 위치를 반환한다. 이 둘을 조합하여, 입력받은 카드를 정렬한 후에, lower_bound를 통해 처음 등장하는 위치를 구하고, upper_bound를 통해 입력받은 숫자보다 큰 위치를 받아, 그 두개의 거리를 구하면, 그것이 개수가 된다.

 

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

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t, temp;
    vector<int> v;

    cin >> t;
    while (t--) {
        cin >> temp;
        v.push_back(temp);
    }
    
    sort(v.begin(), v.end());   

    cin >> t;
    while (t--) {
        cin >> temp;
        cout << upper_bound(v.begin(), v.end(), temp) - lower_bound(v.begin(), v.end(), temp) << ' ';
    }
}