백준-1920

이번 문제는 매우 간단해보이는 문제였다.
입력 값의 범위를 보지 않고 문제를 제출했을 때의 코드는 다음과 같다.

int main()
{
	int N = 0;
	cin >> N;
	unordered_map<int, int> s;
	for (int i = 0; i < N; ++i)
	{
		int num = 0; cin >> num;
		s.insert(make_pair(num, num));
	}

	int M = 0;
	cin >> M;
	vector<int> vec2(M);
	for (int i = 0; i < M; ++i)
		cin >> vec2[i];

	for (int j = 0; j < M; ++j)
	{
		if (s.find(vec2[j]) != s.end()) cout << 1 << endl;
		else cout << 0 << endl;
	}
}

처음 unordered_map을 쓸 때 무작정 O(1)의 시간복잡도를 갖는다고 알고 사용했는데, 사실 최악의 경우 O(N)의 시간복잡도를 가질 수 있었다.
최악의 경우 O(M*N)의 시간복잡도를 가질 수 있는 것이다.

그래서 일반적인 for문을 가지고서는 문제를 해결할 수 없다고 생각해 N번 입력받은 수들을 오름차순으로 나열하여 절반씩 잘라서 확인하는 분할정복, 그 중 이진탐색(Binary Search) 방법을 사용해 보기로 했다.

그 결과는 다음과 같다.

void solve(vector<int>& v, int num, int left, int right)
{
	int mid = (left + right) / 2;
	
	if (left > right)
	{
		cout << "0\n";
		return;
	}
	else {
		if (num < v[mid]) {
			return solve(v, num, left, mid - 1);
		}
		else if (num > v[mid]) {
			return solve(v, num, mid + 1, right);
		}
		else {
			cout << "1\n";
			return;
		}
	}
}

if (left > right)
	{
		cout << "0\n";
		return;
	}

원래 위 부분에서 출력값과 리턴값을 합쳐서

return 0;

이런 식으로 표현하려 했으나 시간초과가 발생하여 원래대로 고치게 되었다.

이번 문제를 풀면서 아직 자료구조에 대한 지식이 많이 부족하고, 알고리즘 구현에 기초가 되는 지식들을 쌓아야겠다는 것을 느꼈다..😭