[백준] 1920번 수 찾기

 

 

 

 

 

문제

 

소스코드

#include<iostream>
#include<algorithm>
#include<array>
constexpr int MAX = 1000000;
int main() {
	// N 은 배열
	// M은 이 배열이 숫자안에 있는지 
	int M, N;
	std::array<int, MAX> n_list;
	std::array<int, MAX> m_list;

	std::cin >> N;
	for (int i = 0; i < N; ++i)
		std::cin >> n_list[i];

	std::cin >> M;
	for (int i = 0; i < M; ++i)
		std::cin >> m_list[i];

		//이진 탐색을 위해서 정렬를 한다. 
		// 컨테이너 크기를 MAX로 했기 때문에 입력한 부분까지만 정렬을 진행한다.
	std::sort(n_list.begin(), n_list.begin() + N, [](auto& lhs, auto& rhs) {
		return lhs < rhs;
		});

	for (int curr = 0; curr < M; ++curr) {
	int min = 0, max = N;
	bool is_number = false;
		while (min <= max) {
			int mid = (min + max) / 2;

			if (n_list[mid] == m_list[curr]) { is_number = true; break; }

			else if (n_list[mid] < m_list[curr])min = mid+1;

			else
				max = mid-1;
		}
		if(is_number)
		std::cout << "1\n";
		else
			std::cout << "0\n";
	}
}

 

 

후기

이진 탐색 2020/01/12 - [자료구조 알고리즘/탐색 알고리즘] - 이진 탐색(Binary Search)을 사용해야 문제 중 가장 기초이다. 알고리즘을 풀기 시작한 이유 중 하나가 탐색 알고리즘 부분이 약해서 인대 이제 가장 기초라고 할 수 있는 문제를 풀면서 시작을 할 수 있었다. 

 

 

 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/1920