백준 2776번: 암기왕 (C++)

문제 링크 : www.acmicpc.net/problem/2776

 

 

문제 자체는 간단한 문제이지만 조금 문제점이 있다. nlogn 복잡도로만 풀면 되는 문제이기에 set을 이용하는 방식과 이분탐색을 이용하는 방식 둘다 통과해야하지만 set으로 풀면 통과가 되지 않는다.(set 자체가 느리기 때문)

 

<알고리즘 + 시간복잡도> 

문제를 읽어보면 정수의 개수만 1000000개이다. 이것을 그냥 배열에 넣어서 순차 탐색으로 수를 찾는다면 1000000*1000000수준의 복잡도가 나온다. 그러므로 방법은 set을 이용하는 방법과, 이분 탐색을 이용하는 방법이 있다.

-set을 이용하는경우 -> 균형 이진 트리 구조임으로 해당 값을 찾는데 logn수준의 복잡도이다.

-이분탐색을 이용하는 경우 -> 역시 분할 정복임으로 logn수준의 복잡도이다.

둘다 전체 알고리즘 복잡도는 nlogn이 되고 결국 1000000*20 = 대강 20000000으로 계산된다. 연산상수 하나당 어떤 값을 넣느냐에 따라서 통과냐 실패냐 결정될 만큼 수가 너무 아슬하게 주어졌다. (보통 1초당 1억번 연산이기 때문)

 

그렇기 때문에 둘 다 시간복잡도 면에서 옳은 방식이지만 set으로 푼 경우는 틀리다고 뜬다.  set방식은 컨테이너 자체 연산속도가 이분탐색보다 느리기 때문에 실패가 뜬다. 결국 이분 탐색으로 풀어야 한다.

 

처음에 수첩1의 정수값을 모두 vector로 받고 정렬한 후 수첩2의 수 하나씩 이분 탐색을 하면 된다.

 

 

<전체 코드>

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

using namespace std;

bool bineary_search(int start, int end, int target,vector<int> &v)
{
	if (start > end)return false;
	int  mid = (start + end) / 2;
	if (v[mid] == target)return true;
	else if (v[mid] < target)return bineary_search(mid + 1, end, target,v);
	else return bineary_search(start, mid - 1, target,v);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int test;
	cin >> test;
	for (int t = 0; t < test; t++)
	{
		vector<int> v;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			int num;
			cin >> num;
			v.push_back(num);
		}
		sort(v.begin(), v.end());
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			int num;
			cin >> num;
			if(bineary_search(0, v.size() - 1, num,v))cout << "1\n";
			else cout << "0\n";
		}
	}
	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.