글 읽기 - [C] 머지소트로 했는데 시간초과 문제 도와주세요..

1004_____ 7년 전 0

5% 이후로 계속 시간 초과가 돼서요..

나름 머리 굴려서 머지 소트를 짜봤는데 잘못한 부분이나 시간을 줄일 수 있는 법 도와주시면 감사하겠습니다.

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

void merge_sort(int start, int end, int *arr){
    if(start >= end)
        return;
    int mid = (start + end) / 2;
    
    merge_sort(start,mid,arr);
    merge_sort(mid+1,end,arr);

    int i,j,k=0;
    int *sort = (int*)calloc(sizeof(int),end - start +1 );
    for(i=start;i<=mid;i++){
        for(j=mid+1;j<=end;j++){
            if(arr[i]>arr[j] && arr[j]!=-1){
                sort[k++]=arr[j];
                arr[j]=-1;
            }
            else if(arr[i]<arr[j] && arr[i]!=-1){
                sort[k++]=arr[i];
                arr[i]=-1;
            }
        }
    }
    if(k<=end){
        for(i=start;i<=end;i++){
            if(arr[i]!=-1)
                sort[k++]=arr[i];
        }
    }
    k=0;
    for(i=start;i<=end;i++){
        arr[i]=sort[k++];
    }
    
    free(sort);
}
int main(){
    int n,i;
    scanf("%d",&n);
    int *arr = (int*)calloc(sizeof(int),n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);
    merge_sort(0,n-1,arr);
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
    free(arr);
    return 0;
}

bupjae 7년 전 1

이 문제의 입력은 "절대값이 1,000,000 보다 작거나 같은 정수" 이기 때문에 음수도 들어올 수 있습니다. -1 같은 걸로 배열의 끝을 표시하면 안됩니다.

1004_____ 7년 전 0

그 점은 간과했네요

좋은 지적 감사합니다

1004_____ 7년 전 0

-1을 -1000001로 고쳤으나 타임아웃은 변하지 않습니다..ㅠㅠ

시간 줄이는 것 도와주시면 감사하겠습니다..

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

void merge_sort(int start, int end, int *arr){
    if(start >= end)
        return;
    int mid = (start + end) / 2;
    
    merge_sort(start,mid,arr);
    merge_sort(mid+1,end,arr);

    int i,j,k=0;
    int *sort = (int*)calloc(sizeof(int),end - start +1 );
    for(i=start;i<=mid;i++){
        for(j=mid+1;j<=end;j++){
            if(arr[i]>arr[j] && arr[j]!=-1000001){
                sort[k++]=arr[j];
                arr[j]=-1000001;
            }
            else if(arr[i]<arr[j] && arr[i]!=-1000001){
                sort[k++]=arr[i];
                arr[i]=-1000001;
            }
        }
    }
    if(k<=end){
        for(i=start;i<=end;i++){
            if(arr[i]!=-1000001)
                sort[k++]=arr[i];
        }
    }
    k=0;
    for(i=start;i<=end;i++){
        arr[i]=sort[k++];
    }
    
    free(sort);
}
int main(){
    int n,i;
    scanf("%d",&n);
    int *arr = (int*)calloc(sizeof(int),n);
    for(i=0;i<n;i++)
        scanf("%d",&arr[i]);
    merge_sort(0,n-1,arr);
    for(i=0;i<n;i++)
        printf("%d\n",arr[i]);
    free(arr);
    return 0;
}

bupjae 7년 전 1

원래 merge sort의 merge 단계는 O(n) 으로 구현해야 하는데, 이 프로그램은 O(n²) 으로 구현하고 있네요.

2중 for 문이 아니라 1중 for문 으로 두 배열을 합치는 방법을 찾아보세요. (1중이기만 한다면 for 문 4~5개 정도 써도 괜찮을 겁니다)

1004_____ 7년 전 0

도움 정말 감사드립니다.

앞으로 다중 포문 쓰는 일을 줄이도록 해야겠어요.. 진짜 감사드립니다!!

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

문제

문제

출처

ICPC

[C] 머지소트로 했는데 시간초과 문제 도와주세요..

1004_____ 7년 전 0

bupjae 7년 전 1

1004_____ 7년 전 0

1004_____ 7년 전 0

bupjae 7년 전 1

1004_____ 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말