[알고리즘문제] 백준 암기왕(2776번) 시간초과

www.acmicpc.net/problem/2776

2776번: 암기왕

수첩1과 수첩2에 각각 정수가 적혀져 있다.

각 수첩에 모두 존재하는 숫자가 있다면 1을 출력 아니라면 0을 출력하는 문제이다.

첫번째로 시도한 케이스는 단순하게 2중 반복문을 이용하여 문제를 제출했다.

코드를 조금씩 수정해 가며 풀어도 2중 반복문(O(n²))으로는 시간 초과가 난다.

좀더 빠른 문제풀이를 위하여 2진 탐색을 했다.

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

using namespace std;

vector<vector<int>> output;

//2분탐색
void binarySearch(vector<int> first, vector<int> second) {
	bool exist = false;
	vector<int> tmp;

	for (int i = 0; i < first.size(); i++) {
		tmp = second;
		int middle = second.size() / 2;
		while(!exist) {
			//first배열의 요소보다 second배열의 중간 요소가 같을 경우
			if (first[i] == tmp[middle]) {
				exist = true;
				tmp.clear();
				break;
			}
			else if (i > middle) {
				break;
			}
			//first배열의 요소보다 second배열의 중간 요소가 더 클 경우 -> 이전 값 push
			else if (first[i] < tmp[middle]) {
				tmp.clear();
				for (int j = 0; j < middle; j++) {
					tmp.push_back(second[j]);
				}
				middle = tmp.size() / 2;
			}
			//first배열의 요소보다 second배열의 중간 요소가 더 작을 경우 -> 이후 값 push
			else if (first[i] > tmp[middle]) {
				tmp.clear();
				for (int j = middle; j < tmp.size(); j++) {
					tmp.push_back(second[j]);
				}
				middle = tmp.size() / 2;
			}
		}

		//탐색 결과가 true
		if (exist == true) {
			exist = false;
			for (int j = 0; output.size(); j++) {
				if (first[i] == output[j][0]) {
					output[j][1] = 1;
					break;
				}
			}
			exist = false;
		}
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i][1] << "\n";
	}
}

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

	int T, N1 = 0, N2 = 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N1;
		vector<int> tmp1(N1);
		for (int j = 0; j < N1; j++){ 
			cin >> tmp1[j];
		}
		cin >> N2;
		vector<int> tmp2(N2);
		for (int j = 0; j < N2; j++) {
			cin >> tmp2[j];
		}

		for (int i = 0; i < tmp2.size(); i++) {
			output.push_back({ tmp2[i], 0 });
		}

		sort(tmp1.begin(), tmp1.end());
		sort(tmp2.begin(), tmp2.end());
		
		binarySearch(tmp1, tmp2);

		tmp1.clear();
		tmp2.clear();
	}

	return 0;
}

2진 탐색하는 binarySearch함수를 만들어서 제출해 봤는데

여전히 시간 초과이다.

tmp vector의 재할당에 시간이 걸린다.

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

using namespace std;

//2분탐색
bool binarySearch(int start, int end, int object, vector<int> v) {
	if (start > end) return false;

	int middle = (start + end) / 2;

	if (v[middle] == object) return true;
	else if (v[middle] < object) return binarySearch(middle + 1, end, object, v);
	else return binarySearch(start, middle - 1, object, v);

	return false;
}

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

	int T, N= 0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		vector<int> v(N);
		for (int j = 0; j < N; j++) {
			cin >> v[j];
		}
		sort(v.begin(), v.end());

		//기준이 되는 2번째 수첩
		cin >> N;
		for (int j = 0; j < N; j++) {
			int object = 0;
			cin >> object;
			if (binarySearch(0, v.size() - 1, object, v)) cout << "1\n";
			else cout << "0\n";
		}
	}

	return 0;
}

위의 코드와 같이 수정했다.

첫번째 수첩의 내용을 vector로 받아 정렬 후, 기준이 되는 2번째 수첩의 숫자를 저장해 둔 vector와 비교하여 이진탐색을 시켰다.

여전히 시간초과이다..

이 문제는 더 효율적인 방법이 있는지 찾아본 후 다시 제출해봐야 겠다