글 읽기 - 1920번 시간초과

kbj40201 4년 전 0

cin, cout은 시간초과라길래 scanf printf 써봐도 시간초과이고 cin.tie(0)써봐도 시간초과인걸로 보아 다른 부분에서 시간초과 원인이 있는 것 같습니다. 제가 놓친 부분이 어딘지 궁금합니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char** argv) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m, min;
	int first[100000];
	int second[100000];
	bool str;
	cin >>n;
	for (int i=0;i<n;i++){
		cin >> first[i];
	}
	cin >>m;
	for (int i=0;i<n;i++){
		cin >> second[i];
	}
	
	sort(first, first+n);
	
	for (int i=0;i<n;i++){
		str=false;
		for(int j=0;j<n;j++){
			if (second[i]==first[j])
				str=true;
			
		}
		if (str==true)
			cout <<"1"<<"\n";
		else
			cout<<"0"<<"\n";
	}
	return 0;
}

djm03178 4년 전 1

놓친 부분은 23, 25번째 줄의 이중 루프가 O(N^2)을 만든다는 점입니다. O(NlogN)에 푸는 방법을 생각해 보세요.

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

문제

문제

출처

ICPC

1920번 시간초과

kbj40201 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말