글 읽기 - 시간초과

okmy729 3년 전 0

시간초과가 나와요. 어떻게 하면 시간을 단축 시킬 수 있나요?? 알려주시면 감사하겠습니다.

제 생각으로는 15~19때문에 일어나는 것 같은데...

#include <bits/stdc++.h>
using namespace std;
long int arr[100005]={},n,m,a,k;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	std::sort(arr,arr+n);
	cin >> m;
	for(int i=0;i<m;i++){
		cin >> a;
		for(int g=0;g<n;g++){
			if(a == arr[g]){
				arr[g]=0;
				k++;
				break;
			}
		}
		if(k > 0){
			cout << "1" << "\n";
			k=0;
			continue;
		}
		else{
			cout << "0" << "\n";
			continue;
		}
	}
}

kms9937 3년 전 1

이진탐색을 활용하시면 시간은 단축시킬 수 있습니다

sonjaewon 3년 전 1

당연히 시간초과죠...

저 코드로는 시간복잡도가 O(100000^2) = O(10000000000) 이므로 이 코드는 100 초 안에도 못 돌아갑니다.

이분탐색을 사용하시면 O(NlogN) 만에 푸실 수 있습니다.

okmy729 3년 전 0

두분 다 감사합니다.

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

문제

문제

출처

ICPC

시간초과

okmy729 3년 전 0

kms9937 3년 전 1

sonjaewon 3년 전 1

okmy729 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말