글 읽기 - 시간초과이유...

wnsrnek3 6년 전 0

충분히 빠르게 binary Search로 구현한거같은데...

예시 결과는 잘나오는데 왜 시간초과가 뜰까요...

(ubuntu linux상에서 해서 배열크기 const아닌 int로 동적으로 잡은건 신경안쓰셔도 될것같습니다...)

#include <cstdio>
#include <cstring>
#include <algorithm>

void binSch(int v, int * arr,int size){
	int l=0, r=size-1;
	int m;
	while(true){
		m = (int) (l+r)/2;
		if (arr[l]==v || arr[m]==v || arr[r]==v) 
		{
			printf("1\n");
			break;
		}
	
		if (arr[l]<v && v<arr[m]) {     // left
			r=m;
		}else if(arr[m]<v && v<arr[r]){ //right
			l=m;
		}else{ printf("0\n"); break;}
		
	}
}

int main(){
	int n;
	scanf("%d",&n);
	int arr[n];
	for(int i=0; i<n; i++) scanf("%d", &arr[i]);
	int m;
	scanf("%d",&m);
	int arr2[m];
	for(int i=0; i<m; i++) scanf("%d", &arr2[i]);

	std::sort(arr,arr+n);
	for(int i=0; i<m; i++)
		binSch(arr2[i],arr,n);

	
	return 0;
}

wondy1128 6년 전 1

binSch 안에 루프(1) 에서 나올 수 있는 조건이 부족하지 않나 생각해봅니다.

// 0 1 2 3 4 5 6 7 8 9

인 조건에서 찾을 값이 우측에 편향되어 있거나 , 사이 값인 경우에

// min mid max

// 0 4 9

// 4 6 9

// 6 7 9

// 7 8 9

// 8 8 9

... 계속 8 8 9 인 상태가 되어서 루프를 종료하지 못하고 돌 것 같습니다.

wondy1128 6년 전 1

코드를 돌려본 결과 16-20 줄 라인에 교체는 값인 r , l = ( ) ; 여기를 수정하고, 종료조건 하나를 넣어주면 될 것 같네요. 인덱스 조건을 벗어난 경우에

수정하여 돌려보니 맞았다고 결과를 보여주네요

		if (arr[l]<v && v<arr[m]) {     // left
			r=m;
		}else if(arr[m]<v && v<arr[r]){ //right
			l=m;
		}

wnsrnek3 6년 전 1

감사합니다!

if (arr[l]<v && v<arr[m]) { // left
r=m-1;
}else if(arr[m]<v && v<arr[r]){ //right
l=m+1;
}else{ printf("0\n");break;}

m은 더이상 볼필요가 없었네요... m-1, m+1로 각각 바꾸어주니 제대로 동작합니다! 감사합니다!!!! ㄷㅇㄴㅎ ㅅㄹㅎㄴㄷ

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

문제

문제

출처

ICPC

시간초과이유...

wnsrnek3 6년 전 0

wondy1128 6년 전 1

wondy1128 6년 전 1

wnsrnek3 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말