C++ / 백준 / 10816 / 숫자 카드 2

문제

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

10816번: 숫자 카드 2

문제풀이

숫자 카드 문제와 다른 점은 숫자가 겹칠 수도 있다는 점이다.

숫자 카드 문제에서 이분 탐색 중에 상근이의 카드와 확인해야 하는 카드값이 같으면 그 인덱스를 기준으로 왼쪽으로, 오른쪽으로 가면서 같은 숫자가 있는지를 탐색하도록 했는데 시간 초과가 뜨길래 검색해보다가 훨씬 좋은 방법을 찾았다.

바로 upper_bound와 lower_bound이다.

정렬된 벡터에서 upper_bound는 (시작 지점, 끝 지점, 찾는 값) 일 때, 찾는 값이 여러 개 있을 때 벡터에서 인덱스가 가장 큰 곳+1을 return 하는 함수이다. 따라서 찾는 값이 아닌 바로 다음수의 위치를 나타낸다.

lower_bound는 해당 숫자가 몇 번째부터 시작하는지를 알려준다.

따라서 upper_bound 값 - lower_bound 값을 빼면 해당 숫자가 몇 개 있는지를 나타낸다.

 

먼저 카드의 숫자를 입력받고, 정렬하고, 확인하는 카드를 입력받는 동시에 upper_bound, lower_bound의 차를 이용하여 카드의 개수를 바로바로 출력하면 된다.

 

코드

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

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

	int N = 0;
	int M = 0;
	int i = 0;
	
	cin >> N;
	vector<int>card(N, 0);

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

	cin >> M;
	sort(card.begin(), card.end());
	int num = 0;

	for (i = 0; i < M; ++i) {
		cin >> num;
		cout << upper_bound(card.begin(), card.end(), num)
			- lower_bound(card.begin(), card.end(), num) << " ";
	}		
}