[백준] 10815 숫자 카드 with C++

문제설명

---

입출력 예제

---

개념

　이 문제는 M개의 숫자 카드 중에서 N개의 숫자 카드와 겹치는 카드가 있는지 찾는 문제다. find 함수를 사용하면 최악의 경우, 시간 복잡도가 O(MN)이 되므로 시간 초과 문제에 걸리기 십상이다. 따라서 이진 탐색을 이용해 시간 복잡도를 O(M logN)으로 개선하여 해결하면 된다. 

---

풀이

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

int main()
{
	std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

	int N, M, n;
	std::vector<int> v;

　카드의 개수 N, M, 숫자 카드 n을 초기화하고, 숫자 카드들을 담을 컨테이너 vector v를 초기화한다.

 

	std::cin >> N;
	for (int i = 0; i < N; i++)
	{
		std::cin >> n;
		v.push_back(n);
	}

	std::sort(v.begin(), v.end());

　N개의 카드들을 벡터에 삽입하고, 이진 탐색을 위해 정렬해준다.

 

	std::cin >> M;
	for (int i = 0; i < M; i++)
	{
		std::cin >> n;
		std::cout << std::binary_search(v.begin(), v.end(), n) << ' ';

　M개의 카드들을 벡터에 차례대로 삽입하는데, 삽입과 동시에 이진 탐색을 하여 값을 출력하면 된다.

 

출처: https://en.cppreference.com/w/cpp/algorithm/binary_search

 

　std::binary_search()는 이진 탐색 알고리즘을 이용해 정렬된 범위에서 원하는 값의 존재 여부를 true, false로 출력하는 함수다. 이때 이진 탐색 알고리즘이란 정렬된 배열에서 특정 값을 찾는 알고리즘이다. 탐색 범위를 반으로 줄여가며 값을 찾을 때까지 반복적으로 탐색하는데, 시간 복잡도가 O(log n)인 것이 특징이다.

 

총합본

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

int main()
{
	std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

	int N, M, n;
	std::vector<int> v;

	std::cin >> N;
	for (int i = 0; i < N; i++)
	{
		std::cin >> n;
		v.push_back(n);
	}

	std::sort(v.begin(), v.end());

	std::cin >> M;
	for (int i = 0; i < M; i++)
	{
		std::cin >> n;
		std::cout << std::binary_search(v.begin(), v.end(), n) << ' ';
	}
}