[백준] 10816번 숫자 카드 2

문제

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

풀이과정

전에 풀었던 숫자 카드는 그냥 카드뭉치에 숫자가 존재하는지의 여부만 판단하면 됐는데 이 문제는 카드뭉치에서 숫자가 몇 개 존재하는지까지 알아야되는 까다로운 문제다.

역시 이진탐색을 이용해서 풀어야되며 내가 전부터 헷갈려 하던 lower_bound와 upper_bound를 쓰면 쉽게 해결할 수 있는 문제다.

예제의 입력을 보자.

6 3 2 10 10 10 -10 -10 7 3

이러한 카드뭉치(vector card)가 있을 경우 lower_bound(card.begin(),card.end(),10)은 10이 존재하는 처음의 위치를 반환하게 된다.

그리고 upper_bound는 10이 마지막으로 존재하는 위치 + 1 을 반환하게 된다.

문제의 경우 upper_bound - lower_bound를 해주면 숫자가 존재하는 개수가 나타나게 된다.

또한, equal_range는 이러한 lower, upper bound들의 값을 pair값으로 반환하게 되며, 아래 소스코드처럼 문제를 해결할 수 있다.

소스코드

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

using namespace std;

#define MAX_N 500001

int N, M;
vector<int> card;
int target[MAX_N];

int main()
{
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int card_num;
        cin >> card_num;
        card.push_back(card_num);
    }

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

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        cin >> target[i];
    }


    for (int i = 0; i<M; i++)
    {
        auto a = equal_range(card.begin(), card.end(), target[i]);
        //cout << upper_bound(card.begin(), card.end(), target[i])-lower_bound(card.begin(),card.end(),target[i]) << " ";
        cout << a.second-a.first << " ";
    }

    return 0;
}