BaekJoon 1920 수찾기

Link https://www.acmicpc.net/problem/1920

소스결과 2012 KB / 76 ms

출처 Baekjoon

언어 C++ 17

분류 이분 탐색

 

설명

N개의 정수가 들어있는 배열 A에서 M개의 값이 들어있는 배열 M에 각각의 값이 N에 존재하는지 확인하는 문제

 

문제 탐색의 속도를 묻는 문제라는 느낌이 강한 문제였다. 그렇다면 방법은 Binary Search 하나밖에 없다.

Binary Search 를 사용하기 위해서는 정렬이 전제로 되기 때문에 먼저 배열 A를 정렬해야한다.

값의 개수가 최대 10만개 라는 점에 유의해서 정렬 방법을 선택하자.

 

정렬이 됬다면 각각의 값을 Binary Search를 통해 값이 존재하는지 확인해 존재하면 1 없으면 0을 출력해주자

 

알고리즘

1. n값과 m값을 받아 주어진 값을 저장하는 벡터를 생성한다.

2. 배열 A를 정렬한다.

3. m 개의 원소가 들어있는 배열을 Binary Search를 통해 값이 존재하는지 확인한다.

 

소스코드

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, m;

	scanf("%d", &n);

	vector<int> numbers(n);

	for (int i = 0; i < n; i++)
		scanf("%d", &numbers[i]);

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

	scanf("%d", &m);

	vector<int> targets(m);

	for (int i = 0; i < m; i++)
		scanf("%d", &targets[i]);

	for (int i = 0; i < m; i++)
	{
		int left = 0, right = n-1;

		while (left < right)
		{
			int mid = (left + right) / 2;
			if (targets[i] < numbers[mid]) right = mid - 1;
			else if (targets[i] > numbers[mid]) left = mid + 1;
			else break;
		}

		printf("%d\n", targets[i] == numbers[(left + right) / 2] ? 1 : 0);
	}

	return 0;
}