글 읽기 - 시간초과..

jjj 7년 전 0

먼저 quick sort로 정렬하고 binary search를 하는데 시간초과가 계속 뜹니다.. 어떻게 해결해야할까요?ㅠㅠ

#include <stdio.h>

int arr[500000];
int partition(int* arr, int left, int right){
    int i=left,j=right,pivot=arr[left];
    int tmp;
    while (1) {
        do i++;while(arr[i]<=pivot && i<=right);
        do j--;while(arr[j]>=pivot && j>left);
        if(i>=j)break;
        tmp = arr[j]; arr[j]=arr[i]; arr[i]=tmp;
    }
    tmp=arr[left],arr[left]=arr[j];arr[j]=tmp;
    return j;
}
void quick_sort(int *arr, int left, int right){
    if(left<right){
        
        int j= partition(arr, left, right+1);
        quick_sort(arr, left, j-1);
        quick_sort(arr, j+1, right);
    }
}
int binary_search(int count, int left, int right, int findNum){
    int mid=(left+right)/2;
    int result=0;
    if (left>right) {
        return count;
    }
    else{
        if (arr[mid]<findNum) {
            result = binary_search(count, mid+1, right, findNum);
        }
        else if(arr[mid]>findNum){
            result = binary_search(count, left, mid-1, findNum);
        }
        else if (arr[mid]==findNum){
            result++;
            result+=binary_search(count, mid+1, right, findNum);
            result+=binary_search(count, left, mid-1, findNum);
        }
        return result;
    }
}
int main(int argc, const char * argv[]) {

    int N,M;
    int brr[500000];
    int left,right;
    scanf("%d",&N);
    for (int i=0; i<N; i++) {
        scanf("%d", &arr[i]);
    }
    quick_sort(arr, 0, N-1);

    scanf("%d", &M);
    for (int i=0; i<M; i++) {
        scanf("%d", &brr[i]);
    }
    for (int i=0; i<M; i++) {
        left=0;
        right=N;
        printf("%d ",binary_search(0, left, right, brr[i]));
    }
    return 0;
}

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

문제

문제

출처

ICPC

시간초과..

jjj 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말