글 읽기 - 1920번 시간초과 질문입니다.

zakelstorm 8년 전 0

퀵소트와 바이너리소트로 가능한 기동시간 최소로 했는데

계속 시간초과가 뜨는데 어느 함수부분에서 시간을 그렇게 잡아먹게 생겼나요?

#include <stdio.h>
void InitArr(int* arr,int T);
void QSort(int* arr,int start,int end);
void Swap(int* arr,int a,int b);
void Search(int* arr1,int* arr2,int N,int M);
int BSearch(int* arr1,int left,int right,int target);

int main(){
    int i,N,M;
    int A[100001];
    int B[100001];
    
    //A
    scanf("%d",&N);
    InitArr(A,N);
    QSort(A,1,N);
	
	//B
    scanf("%d",&M);
    InitArr(B,M);
    
    Search(A,B,N,M);
    return 0;
}
void InitArr(int* arr,int T){
 int i;
 for(i=0;i<T;i++)
  scanf("%d",&arr[i+1]);
}
void QSort(int* arr,int start,int end){
 int pivot = arr[start];
 int left = start+1;
 int right = end;
 if(start<end){
  while(left<=right){
   while(arr[left]<=pivot && left < end){
    left++;
   }
   while(arr[right]>=pivot && right > start){
    right--;
   }
   if(left<=right){
    Swap(arr,left,right);
   }
  }
 Swap(arr,right,start);
 QSort(arr,start,right-1);
 QSort(arr,right+1,end);
 }
}
void Swap(int* arr,int a,int b){
 int temp;
 temp = arr[a];
 arr[a]= arr[b];
 arr[b]=temp;
}

void Search(int* arr1,int* arr2,int N,int M){
	int i,a;
	
	for(i=1;i<=M;i++){
		a=BSearch(arr1,1,N,arr2[i]);
		if(a==-1){
			printf("0\n");
		}else{
			printf("1\n");
		}
	}
}

int BSearch(int* arr,int left,int right,int target){
	int mid;
	while(1){
		if(left > right) return -1;
		mid = (left+right)/2;
		if(arr[mid]==target){
			return mid;
		}else if(arr[mid]>target){
			right = mid-1;
		}else{
			left = mid+1;
		}
	}
}

kesakiyo 8년 전 0

pivot을 랜덤으로 잡아봐주는건 어떨까요?

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

문제

문제

출처

ICPC

1920번 시간초과 질문입니다.

zakelstorm 8년 전 0

kesakiyo 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말