(C++) 백준 10816번 - 숫자 카드 2

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

문제

> 상근이는 정수 하나가 적혀져 있는 숫자 카드 N개를 가지고 있다. 
> 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성해라.

접근

이진탐색을 사용하여 찾고자하는 수의 개수를 구한다.
이진탐색의 lower_bound, upper_bound를 사용한다.

문제해결

> 입력으로 주어진 N개의 숫자카드를 먼저 입력받아 card 벡터에 넣는다.
> 이진 탐색을 위해 해당 벡터를 정렬해준다.
> 결과를 담을 벡터를 선언해주고 상근이의 카드를 입력받아준다.
tmp로 카드를 입력받고 해당 카드를 lower_bound에 넣어 해당 카드보다 같거나 큰 카드가 시작하는 인덱스를 받아오고
upper_bound에 넣어 해당 카드를 초과하는 인덱스를 받아온다.
> upper_bound의 값에서 lower_bound의 값을 빼면 해당 카드와 같은 카드의 개수가 나온다.
이를 결과 벡터에 순서대로 넣고 출력한다.

코드

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

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

	int N, M;
	cin >> N;

	vector<int> card(N);
	for (int i = 0; i < N; i++) cin >> card[i];

	sort(card.begin(), card.end());
	vector<int> cardcnt;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int tmp;
		cin >> tmp;

		auto low = lower_bound(card.begin(), card.end(), tmp);
		auto upper = upper_bound(card.begin(), card.end(), tmp);

		cardcnt.push_back(upper - low);
	}
	for (auto& a : cardcnt) cout << a << " ";
}

후기

처음에 탐색알고리즘을 써서 하려다 그냥 벡터에서 특정원소의 개수를 구하는 명령어 count를 써서 했다.
cardcnt.push_back(count(card.begin(), card.end(), tmp));
이렇게 햬서 제출했더니 시간초과가 발생했다. 알고보니 tmp로 카드를 입력받은뒤 이 카드를 N개의 카드 벡터와 처음부터 끝까지 대조하기 때문에, 즉, 전탐색을 해서 시간초과가 났다.
이진탐색은 left, right, mid를 잡아두고 범위를 좁혀가며 탐색하는 방식으로 구현하는거만 알고 있었는데, 이진탐색에 이런 lower, upper_bound기능이 있는줄 처음알았다. 좋은 기능을 새로 알게됐다.