ZEROONE 해결 방법 질문드립니다.

  • tyjk32
    tyjk32

    ZEROONE 문제에서 제 생각은 배열의 해당 범위만을 MergeSort

    해서 맨앞과 맨뒤의 값만을 비교하여 다르면 No, 같으면 Yes가

    나오도록 했습니다.

    그런데 계속 시간초과가 나오던데, 방법이 잘못된 것인지 소스코드에

    문제가 있는 것인지 해결 방법에 대한 조언좀 부탁드리겠습니다.

    #include <stdio.h>
    #include <string.h>
    
    #define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
    #define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
    
    void merge(char *arr, char *arr2, int low, int mid, int high);
    void mergeSort(char *arr, char *arr2, int low, int high);
    
    int main(void)
    {
        char arr[1000001], arr2[1000001];
        int n, i, j;
        int a, b;
    
        scanf("%s %d", arr, &n);
    
        for(a = 0; a < n; a++)
        {
            memset(arr2, 0, 1000001);
            scanf("%d %d", &i, &j);
            mergeSort(arr, arr2, MIN(i, j), MAX(i, j));
    
            if(arr2[0] != arr2[j - i])
            {
                printf("No\n");
            }
            else
            {
                printf("Yes\n");
            }
        }
    
        return 0;
    }
    
    void mergeSort(char *arr, char *arr2, int low, int high)
    {
        int mid;
    
        if(low < high)
        {
            mid = (low + high) / 2;
            mergeSort(arr, arr2, low, mid);
            mergeSort(arr, arr2, mid + 1, high);
            merge(arr, arr2, low, mid, high);
        }
    }
    
    void merge(char *arr, char *arr2, int low, int mid, int high)
    {
        int i = low;
        int j = mid + 1;
        int k = low;
    
        while(i <= mid && j <= high)
        {
            if(arr[i] < arr[j])
            {
                arr2[k++] = arr[i++];
            }
            else if(arr[i] >= arr[j])
            {
                arr2[k++] = arr[j++];
            }
        }
    }
    

    10년 전
2개의 댓글이 있습니다.
  • 일루
    일루

    방법의 문제입니다. 최대 100만개 정렬을 10만번 한다는 건데 시간제한에 걸립니다.


    10년 전 link
  • tyjk32
    tyjk32

    아 방법을 다시생각해봐야겠네요..감사합니다 ^^


    10년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.