글 읽기 - 시간초과가 나는 이유가 궁금합니다

lantern456 1년 전 0

c로 풀었을땐 초과가 안나왔는데 c++로 풀려고 했더니 초과가 뜨네요...

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

using namespace std;

int BinarySearch(vector<int>a, int key, int n) {
	int low, mid, high;

	low = 0;
	high = n - 1;

	while (1) {
		mid = (high + low) / 2;

		if (a[mid] == key) return 1;
		if (a[low] == key) return 1;
		if (a[high] == key)  return 1;

		if (a[mid] < key) low = mid + 1;
		else high = mid - 1;
		
		if (high <= low) return 0;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, v;
	
	vector<int>a;
	vector<int>arr;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> v;
		a.push_back(v);
	}

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

	cin >> m;

	for (int i = 0; i < m; i++) {
		cin >> v;
		arr.push_back(v);
		arr[i] = BinarySearch(a, arr[i], n);
	}
	for (int i = 0; i < m; i++) {
		cout << arr[i] << "\n";
	}
	return 0;
}

prarie 1년 전 2

한 번 함수 매개변수에서 vector<int> a 말고 vector<int> &a 로 해보세요

백터를 복사하는데 o(n)이 걸려서 시간초과가 날 수 있습니다

lantern456 1년 전 0

아하 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 나는 이유가 궁금합니다

lantern456 1년 전 0

prarie 1년 전 2

lantern456 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말