7-1 부품 찾기

이진 탐색 문제) 부품 찾기

1. 문제

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

N=5
[8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3
[5, 7, 9]

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

2. 입력

• 첫째 줄에 정수 N이 주어진다. (1<=N<=1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다. (1<=M<=100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 10억 이하이다.

3. 출력

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

4. 풀이 1

• 가장 먼저 생각이 든 풀이
• 배열을 선언하여 true/false로 만들어 준다.
• target을 입력받아 true/false에 맞게 결과를 출력한다.
• 입력을 타이핑 하다보니 M개의 정수의 값이 N개의 정수보다 커서 N개의 정수를 초과하는 값을 처리하는 구문을 추가하였다.

5. 코드 1

#include <iostream>
#include <vector>

using namespace std;

int n, m;
bool arr[1000001];


int main() {
	cin >> n;
	
	for (int i = 0; i < n; i++){
		int tmp;
		cin >> tmp;
		arr[tmp] = true;
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		string answer;
		int target;
		cin >> target;
		if (target <= 1000000 && arr[target])
			cout<<"yes ";
		else
			cout<<"no ";
	}
}

6. 풀이 2

• 그래도 이진탐색 단원이라 이진탐색으로 풀기로 했다.
• 입력받는 값을 배열 인덱스로 쓰지 않고 직접 배열에 추가하기로 했다.
• 배열을 두 개 만들고 각각 값을 입력 받은 후 탐색해야 하는 배열은 정렬하고 이진 탐색을 했다.
  라고 썼는데 타겟 배열은 필요 없을 것 같다.
세상 최고 멍청하게 arr[mid]를 안 쓰고 그냥 mid라고 써서 수정했다.
그냥 mid라고 했는데 답이 정확하게 반대로 나와서 등호 반대로 쓴 줄 알았던게 유우머다..

7. 코드 2

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

using namespace std;

int n, m;
vector<int> arr;

bool binarySearch(int target, int start, int end) {
	if (start > end) return false;

	int mid = (start + end) / 2;

	if (arr[mid] == target) return true;
	else if (arr[mid] > target) return binarySearch(target, start, mid - 1);
	else return binarySearch(target, mid + 1, end);
}

int main() {
	cin >> n;
	
	for (int i = 0; i < n; i++){
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

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

	cin >> m;
	for (int i = 0; i < m; i++) {
		int target;
		cin >> target;
		
		if (binarySearch(target, 0, n))
			cout << "yes ";
		else
			cout << "no ";
	}
}