글 읽기 - c++ 시간초과 문제로 골치 아픕니다.

cks1091 2년 전 0

제가 어느 부분에서 시간 초과가 나는지 잘 모르겠습니다. 이분 탐색에서 문제가 생긴 건가요?

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

int arr[100000];
int main(){
	int n,m,k,r=0,left=0,right=0;
	cin>>n;
	right=n-1;
	for(int i=0;i<n;i++){
	cin>>arr[i];
	}
	sort(arr,arr+n);
	cin>>m;
	for(int j=0;j<m;j++){
		r=0;
		left=0;
		right=n-1;
		cin>>k;
		while(left<=right){
		int mid = (left+right)/2;
		if (arr[mid]>k){
			right=mid-1;
		}
		else if (arr[mid]<k){
			left=mid+1;
		}		
		else{
			r++;
			cout<<"1"<< '\n';
			break;
		}
		}
		if(r==0){
			cout<<"0"<< '\n';
		}
	}	
	return 0;
}

bupjae 2년 전 0

cin 과 cout 를 번갈아가면서 사용할 경우 cout 에 매번 flush 연산이 발생합니다.

flush 연산은 상당히 무거운 연산으로, 인터렉티브 이외의 문제에서는 성능만 떨어뜨리는 꼴이 됩니다.

이런 현상을 막으려면 cin.tie(nullptr); 로 cin 과 cout 의 의존관계를 끊으면 됩니다.

cks1091 2년 전 0

감사합니다!! 덕분에 해결했습니당

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

문제

문제

출처

ICPC

c++ 시간초과 문제로 골치 아픕니다.

cks1091 2년 전 0

bupjae 2년 전 0

cks1091 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말