[C/C++] BOJ(백준) 2776 "암기왕" 문제 풀이 & 소스 코드 (feat. 이진탐색)

#문제정보

출처 : https://www.acmicpc.net/problem/2776

난이도 : 실버3

사용된 알고리즘 : 이진탐색 알고리즘 

#문제분석

단순 중첩 for로 돌리면 시간초과(TLE)가 나기에, 이진탐색 알고리즘(binary search)을 이용해 풀이했습니다.

C++ STL의 <Algorithm> 라이브러리는  binary search 알고리즘을 지원하지만, 연습용으로 직접 이진탐색을 구현했습니다.

int binSearch(int arr[], int len, int key)
{
	int l = 0;
	int r = len - 1;
	int m;
	
	while (l <= r)
	{
		m = l + (r-l)/2;
		if (key == arr[m]){
			return 1;
		}
		else if (key < arr[m]){
			r = m - 1;
		}
		else{
			l = m + 1;
		}
	}
	
	return 0;
}

* 굳이 구현하지 않고 STL이 제공하는 이진탐색 함수를 사용해도 결과는 동일합니다.

#소스코드

_1 이진탐색 직접구현

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000001];
int note[1000001];

int binSearch(int arr[], int len, int key)
{
	int l = 0;
	int r = len - 1;
	int m;
	
	while (l <= r)
	{
		m = l + (r-l)/2;
		if (key == arr[m]){
			return 1;
		}
		else if (key < arr[m]){
			r = m - 1;
		}
		else{
			l = m + 1;
		}
	}
	
	return 0;
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int N;
		scanf("%d", &N);
		for (int i = 0 ; i < N ; ++i)
		{
			scanf("%d", &arr[i]);
		}
		
		sort(arr, arr+N);
		
		int M;
		scanf("%d", &M);
		for (int j = 0 ; j < M ; ++j)
		{
			scanf("%d", &note[j]);
		}

		for (int i = 0 ; i < M ; ++i)
		{
			int tmp = binSearch(arr, N, note[i]);
			printf("%d\n", tmp);
		}
	}
	return 0;
}

 

_2 STL Binary_Search 이용

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1000001];
int note[1000001];

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int N;
		scanf("%d", &N);
		for (int i = 0 ; i < N ; ++i)
		{
			scanf("%d", &arr[i]);
		}
		
		sort(arr, arr+N);
		
		int M;
		scanf("%d", &M);
		for (int j = 0 ; j < M ; ++j)
		{
			scanf("%d", &note[j]);
		}

		for (int i = 0 ; i < M ; ++i)
		{
			int tmp = binary_search(arr, arr + N, note[i]);
			printf("%d\n", tmp);
		}
	}
	return 0;
}