글 읽기 - [C언어] 이진탐색 시간초과 질문입니다!

sc3289 2년 전 0

정렬 직접 다 하고 이진탐색을 한 후 수가 있다면

근처 index 서칭하면서 수를 찾는 식으로 구현했습니다.

시간 초과가 걸릴만한 부분은 counting 함수에서 같은 수를 찾는게 아닐까 합니다.

이것도 worst case의 경우 O(N)이라고 생각하는데

여기서 시간초과가 뜨는게 맞다면

이진탐색으로 풀 경우 저 방법외에 시간을 줄일 수 있는 방법이 있을까요?.....

#include <stdio.h>
#include <stdlib.h>

void merge(int*,int*,int,int);
void merge_sort(int*,int*,int,int,int);
int binary_search(int*,int,int,int);
void counting(int*,int,int);

int main()
{
    int n;
    scanf("%d",&n);
    int *num = malloc(sizeof(int)*n);
    int *temp = malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
        scanf("%d",&num[i]);
    merge(num,temp,0,n-1);
    int m,buf,val;
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d",&buf);
        val = binary_search(num,0,n-1,buf);
        if(val == -1)
            printf("0 ");
        else
            counting(num,val,n-1);
    }
    free(num);
    free(temp);
}

void counting(int* arr, int index,int last)
{
    int cur=index,count=0;
    while(cur>=0)
    {
        if(arr[cur] == arr[index])
        {
            count++;
            cur--;
        }
        else
            break;
    }
    cur = index +1;
    while(cur<=last)
    {
        if(arr[cur] == arr[index])
        {
            count++;
            cur++;
        }
        else
            break;
    }
    printf("%d ",count);
    return;
}

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

void merge(int *arr,int* buf,int left, int right)
{
    if(left<right)
    {
        int mid = (left+right)/2;
        merge(arr,buf,left,mid);
        merge(arr,buf,mid+1,right);
        merge_sort(arr,buf,left,right,mid);
    }
    return;
}

void merge_sort(int *arr,int*buf, int left, int right, int mid)
{
    int i=left,j=mid+1,k=left,l;
    while(i<=mid && j<=right)
    {
        if(arr[i]<arr[j])
            buf[k++] = arr[i++];
        else
            buf[k++] = arr[j++];
    }
    if(i>mid)
    {
        for(l=k;l<=right;l++)
            buf[l] = arr[j++];
    }
    else
    {
        for(l=k;l<=right;l++)
            buf[l] = arr[i++];
    }
    for(l=left;l<=right;l++)
        arr[l] = buf[l];
    return;
}

ehdrmsl2001 2년 전 1

lower_bound와 upper_bound로 푸는 문제였던 거 같네요

이진 탐색과 비슷하게 구현할 수 있으니 한 번 찾아보세요

kimnamu 2년 전 1

한번 카운팅한 숫자는 memoization해둬서 다시 카운팅하지 않도록 해야할것 같아요.

map을 사용하면 될것 같은데, 근데 그렇게되면 binary search하지 않고 map만 사용해도 풀린다는건 안비밀입니다.

sc3289 2년 전 0

이진탐색 이후에 저렇게 카운팅하는 과정이 추가된다고 해도 O(N) 추가니까 크게 상관 없을 것 같았는데 한번 카운팅 했던게 worst case로 여러번 들어오면 문제가 되긴 하겠네요...

upper_bound lower_bound 랑 map 을 아직 몰라서 이진탐색으로 도전해봤는데 찾아서 공부해봐야겠군요! 감사합니다

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

문제

문제

출처

ICPC

[C언어] 이진탐색 시간초과 질문입니다!

sc3289 2년 전 0

ehdrmsl2001 2년 전 1

kimnamu 2년 전 1

sc3289 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말