[BOJ/백준 10816][C++] 숫자 카드 2

문제

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

백준 10816

 

문제 내용

숫자 카드들을 입력받고 수를 입력받아, 그 수에 해당하는 숫자 카드의 개수가 몇 개인지를 출력하면 된다.

이때 숫자 카드의 개수는 500,000까지이고, 숫자 카드에 적혀있는 정수는 -10,000,000~10,000,000이다.

입력받는 수 또한 500,000개까지 주어질 수 있다.

 

문제 풀이

배열을 크게 선언해두고, 있으면 값을 증가시키는 방법은 사용할 수 없다.

숫자 카드에 적힌 정수의 범위가 너무 크기 때문이다.

 

이 문제는 이분탐색을 사용하면 좋다.

이분탐색이라 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법으로 탐색 전에 반드시 정렬을 해두어야 한다.

이분 탐색과 관련된 함수로는 binary_search, lower_bound, upper_bound 등이 있다.

binary_search는 값이 범위 내에 존재하는지 여부를 반환하며, lower_bound와 upper_bound는 아래와 같다.

lower_bound: 타겟이 들어갈 수 있는 가장 왼쪽 위치 반환
upper_bound: 타겟이 들어갈 수 있는 가장 오른쪽 위치 반환

 

이 문제 또한 숫자 카드를 입력 받은 뒤, 정렬을 진행한다.

이후 upper_bound 결과 - lower_bound 결과를 구하면 쉽게 입력 받은 수가 몇 개나 포함되어 있는지를 구할 수 있다.

 

코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    int m, tmp;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> tmp;

        cout << upper_bound(arr.begin(), arr.end(), tmp) - lower_bound(arr.begin(), arr.end(), tmp) << ' ';
    }
}