[이진 탐색] 부품 찾기

문제 설명

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 다음 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

이때 손님이 요청한 순서대로 부품을 확인해 부품이 있으면 yes를 없으면 no를 출력한다. 구분은 공백으로 한다.

입력 조건

첫째 줄에 정수 N이 주어진다.
둘째 줄에 공백으로 구분하여 N개의 정수가 주어진다.
셋째 줄에는 정수 M이 주어진다.
넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다.

출력 조건

첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를 없으면 no를 출력한다.

c++ 코드

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

int binarySearch(vector<int>& v, int target, int start, int end)
{
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (v[mid] == target) return mid;
		else if (v[mid] > target) end = mid - 1;
		else start = mid + 1;
	}
	return -1;
}
int main()
{
	int n, m;
	vector<int> v;
	vector<int> v2;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end()); // 이진 탐색을 수행하기 위해 사전에 정렬 수행
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int y;
		cin >> y;
		v2.push_back(y);
	}
	for (int i = 0; i < m; i++)
	{
		int result = binarySearch(v, v2[i], 0, n - 1);
		if (result != -1)
			cout << "yes" << " ";
		else
			cout << "no" << " ";
	}
	
}

set 컨테이너를 이용

set 컨테이너의 특징

1. 숫자든 문자든 중복을 없앤다.
2. 삽입되는 순서에 상관없이 정렬되서 입력이 된다.

삽입과 삭제가 용이, 자료를 찾는 것도 준수함.

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

int main()
{
	int n, m;
	set<int> s;
	vector<int> v;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		s.insert(x); //set에 insert
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int y;
		cin >> y;
		v.push_back(y);
	}
	for (int i = 0; i < m; i++)
	{
		if (s.find(v[i]) != s.end())
			cout << "yes" << " ";
		else
			cout << "no" << " ";
	}
}