글 읽기 - 시간초과 관련하여 질문드립니다~

allgoodlife 7년 전 1

m 장의 카드를 입력받고 vector<int> have에 집어넣고

n장의 카드가 들어올 때마다 find함수를 사용하여 해당 카드가 have 벡터 안에 있는지 검사하도록했습니다.

시간초과가 나는데, 더 줄일 수 있는 방법이 있을까요?

제가 알기론 STL을 이용하여 sort정렬 후 find하면 binary search를 해서 O(nlogn)이 나올 것 같은데,

결과를 보니 아닌것 같네요..ㅠ

조언부탁드립니다.

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

using namespace std;
int main(void){
	int n, m;
	cin >> n;
	vector<int> have(n);
	for (int i = 0; i < n; i++)
	{
		cin >> have[i];
	}
	int tmp;
	cin >> m;
	sort(have.begin(), have.end());
	for (int i = 0; i < m; i++)
	{
		cin >> tmp;
		if (find(have.begin(), have.end(), tmp) == have.end()){
			cout << "0 ";
		}
		else{
			cout << "1 ";
		}
		
	}

	return 0;
}

sang7 7년 전 1

네 Find는 O(N) 이죠

정렬후 binary search를 사용해 보세요

sang7 7년 전 1

그리고 cin cout 하시면 시간초과 나요

allgoodlife 7년 전 0

감사합니다:) 해결되었습니다.

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

문제

문제

출처

ICPC

시간초과 관련하여 질문드립니다~

allgoodlife 7년 전 1

sang7 7년 전 1

sang7 7년 전 1

allgoodlife 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말