[백준 10816] 숫자 카드 2

문제

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

10816번: 숫자 카드 2

 

 

문제 분석

우선 가지고 있는 카드의 개수와 그 카드의 숫자가 정해지고, 

 

또 특정 수가 들어오고 그 카드가 이전에 입력 받은 카드에서 몇개 존재하는지 확인하는 문제이다. 

 

 

알고리즘 설계

우선 몇번 돌아야하는지 알고 있는 변수와, 입력 받을 정수형 변수 2개와 입력 받은 값을 모두 넣어줄 vector를 하나 선언해준다. 

 

몇번 반복할지 입력 받고 안에서 입력을 한번 더 받아 vector에 넣어준다. 

 

반복이 끝났다면 정렬해준다. 

 

이후 몇번 반복할지 다시 입력 받고 그 다음 입력을 한번 더 받아 upper_bounce한 값에 lower_bounce한 값을 빼주고, 그 값을 출력한다. 

 

 

유의점

이 문제는 개인적으론 map으로 푸는 것이 좀 더 쉬웠던거 같다. 다만 아래처럼 이분 탐색으로 푼다면 이진탐색에 대한 이해도가 필요하다. 

 

 

코드 

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

using namespace std;

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

	int loop, input;
	vector<int> vec;

	cin >> loop;
	while (loop--)
	{
		cin >> input;
		vec.push_back(input);
	}

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

	cin >> loop;
	while (loop--)
	{
		cin >> input;
		cout << upper_bound(vec.begin(), vec.end(), input) - lower_bound(vec.begin(), vec.end(), input) << ' ';
	}
}