[백준 C++] 1920 : 수 찾기

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

첫번째로 주어진 N개의 정수 사이에, M개로 주어진 정수들이 포함되어 있는지 확인하는 문제이다.

이분 탐색으로 해결하지 않으면 시간 초과에 걸릴 가능성이 높기 때문에 정렬 후 이분탐색으로 구현하였다.

---

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

using namespace std;

vector<int> list;
vector<int> input;

int findValue(int value, int v1, int v2)
{
	if (v1 > v2)
		return 0;

	int mid = (v1 + v2) / 2;

	if (value == list.at(mid))
		return 1;
	else if (value > list.at(mid))
		return findValue(value, mid + 1, v2);
	else
		return findValue(value, v1, mid - 1);
}

int main()
{
	int N, M;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		list.push_back(temp);
	}

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		int temp;
		cin >> temp;

		input.push_back(temp);
	}

	sort(list.begin(), list.end());

	for (int i = 0; i < M; i++)
		cout << findValue(input[i], 0, N - 1) << '\n';

	return 0;
}

이번 문제를 풀면서 Sort함수에 대해 알게된 사실이 있다.

Quick Sort에서 최악의 경우 O(N^2)인데, C++ STL Sort 함수는 최악의 경우를 대비하여 알고리즘에 변형을 주었기 때문에 시간복잡도 O(N logN)을 보장한다고 한다.

앞으로 정렬할 일이 있으면 바로 Sort 함수를 사용하면 될 것 같다.