글 읽기 - c++ 시간초과 질문입니다.

spacein1001 4년 전 0

시간초과가 나서 이유를 짐작해보니

시간복잡도가 O(N^2)라서 그러는것 같습니다.

O(n log n) 이하로 줄이려면

2중 for문이 아닌 아예 다른 방법으로 접근해야할까요 ???

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

int arr[100001],brr[100001];
int result;

main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL); 
	
	int N,M;
	cin >> N;
	
	for(int i=1;i<=N;i++)
	{
		cin >> arr[i];
	}
	
	cin >> M;
	
	for(int j=1;j<=M;j++)
	{
		cin >> brr[j] ;
		
		result = false;
		
		for(int i=1;i<=N;i++)
		{
			while(1)
			{
				if(brr[j] == arr[i])
				{
					result = true;
					break;
				}
				break;
			}
		}       /////////   O(N^2)  XXXXXXXXXX
		
		cout << result << "\n";
	}
	
}

djm03178 4년 전 0

이분 탐색에 대해 알아보세요.

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

문제

문제

출처

ICPC

c++ 시간초과 질문입니다.

spacein1001 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말