글 읽기 - sort 랑 binary search 를 이용했는데 시간초과가 나네요..

specialjin1 6년 전 0

아무리 생각해도 시간복잡도를 잘못 계산하지 않았는데 시간초과가 떠버립니다

sort랑 Binary search면 (NlogN + MlogN) 가 맞지 않나요!

코드를 잘못 작성한 것 같진 않은데....... 진짜 모르겠네요! 뭐가 문제인지.....

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

int N, M, arr[100010], num;


int binSearch(int front, int end, int num) {
	int mid = (end + front) / 2;
	if (front>end) return 0;
	if (num < arr[mid]) binSearch(front, mid-1, num);
	else if(num > arr[mid]) binSearch(mid+1, end, num);
	else return 1;
}

int main()
{
	cin >> N;
	for (int i = 0;i < N;i++)
		cin >> arr[i];
	sort(arr,arr+N);
	cin >> M;
	for (int i = 0;i < M;i++) {
		cin >> num;
		cout << binSearch(0, N-1, num) << ' ';
	}
}

djm03178 6년 전 1

그냥 cin과 cout을 번갈아서 사용할 경우 출력 때마다 flush가 발생하기 때문에 아주 많은 시간이 걸립니다.

main 함수 시작할 때 ios_base::sync_with_stdio(false); cin.tie(0); 을 넣고 시작해보세요.

specialjin1 6년 전 1

감사합니다! 바로 해결 됬어요!!! 자신이 미워지려던 참이었는데...ㅠ

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

문제

문제

출처

ICPC

sort 랑 binary search 를 이용했는데 시간초과가 나네요..

specialjin1 6년 전 0

djm03178 6년 전 1

specialjin1 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말