[백준] 1920: 수 찾기

문제 링크

https://www.acmicpc.net/problem/1920

접근 방식 / 풀이

이분탐색을 사용해야만 시간초과가 되지 않는 문제다.
1년 전에 시도했다가 포기했던 문제인데, 클래스 2+를 따기 위해 다시 도전해봤다.
비록 지금은 STL을 사용해서 풀기는 했지만, 나중에는 구현으로도 풀어보고 싶은 문제다.

내가 사용한 STL은 set이다.

set 의 특징

1. 중복되는 값을 가지는 원소는 존재하지 않는다.
   (여러 번 insert해도 단 하나만 존재한다.)
2. 자동으로 정렬이 되어있다. (default: 오름차순)
3. Binary Search Tree 구조를 가지고 있기 때문에
   원소를 삽입, 삭제, 탐색할 때, $O(\log N)$의 시간복잡도를 갖는다.

따라서, 찾을 값들은 set에 전부 저장한 뒤, find를 했을 때의 리턴되는 iterator가 end()(: 제일 마지막 원소의 다음 위치) 가 아니라면, 해당 값은 set에 존재한다는 뜻이기 때문에 1을 출력한다.

---

답안 코드 링크 (Github)

Github Solution Link

정답 코드 (C++)

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

using namespace std;
void	fastio(void);

int main(void)
{
	int	n, m, tmp;
	set<int>	list;
	vector<int> comp_list;

	fastio();
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		list.insert(tmp);
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> tmp;
		comp_list.push_back(tmp);
	}
	for (int i = 0; i < m; i++)
	{
		if (list.find(comp_list[i]) != list.end())
			cout << "1\n";
		else
			cout << "0\n";
	}
}

void	fastio(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}