[백준 알고리즘][C++] 이분 탐색(binary search) - 2776번 암기왕

안녕하세요~

​

이번시간에는 2776번 암기왕 문제를 풀어보려고 합니다.

 

 

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

 

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

 

예제 입력 1

1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

정답 코드

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> note1;
int N, M, T;

void solve(int target)
{
	//수첩2를 기준으로 이분 탐색으로 수첩1에 있는지 확인
	int start = 0;
	int end = note1.size()-1;
	bool isInNote = false;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (target == note1[mid])
		{
			isInNote = true;
			break;
		}
		if (target > note1[mid])
		{
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
		}
	}
	//수첩 1에 있으면 1을 출력
	//cout << isInNote << endl;
	printf("%d\n", isInNote);
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(NULL);
	//cout.tie(NULL);
	scanf("%d", &T);
	for (int test = 0; test < T; test++)
	{
		//cin >> N;
		scanf("%d", &N);
		int val = 0;
		for (int i = 0; i < N; i++)
		{
			//cin >> val;
			scanf("%d", &val);
			note1.push_back(val);
		}
		//수첩1에 있는 값들을 오름차순으로 정렬
		sort(note1.begin(), note1.end());
		cin >> M;
		for (int i = 0; i < M; i++)
		{
			//cin >> val;
			scanf("%d", &val);
			solve(val);
		}
		note1.clear();
	}
}