백준 링크 : https://www.acmicpc.net/problem/1920

문제 개요

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 문제이다.

아이디어

• 배열을 오름차순으로 정렬한다.
  • std::sort함수를는 $O(n \log n)$이다.
• 이분탐색으로 해당 값이 존재하는지 판단한다.
  • 이분 탐색은 $O(\log n)$이다. → std::binary_search함수

주의사항

• 최대입력범위가 100,000이므로 $O(n^2)$ 알고리즘으로는 해결할 수 없음을 인지한다.
  • 보통 2중 for문을 통해서 문제를 해결하려고 하는데, 2중 for문으로 순회를 하게 되면 시간 복잡도는 $O(n^2)$이 나오게 된다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> v;
int main()
{
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		v.push_back(temp);
	}
	
	cin >> m;
	sort(v.begin(), v.end());
	for(int i = 0; i < m; i++)
	{
		int temp;
		cin >> temp;
		cout << binary_search(v.begin(), v.end(), temp) << "\\n";
	}
	
  return 0;
}

후기

문제를 보면 브루트포스가 떠오르지만 최대입력값을 잘 인지한다면 함정을 잘 피해갈 수 있던 문제였다. 마침 binary_search함수도 알고 있어서, 간결하며 효율적으로 문제를 해결할 수 있었다.