글 읽기 - 이거 해결하시는 분 무적으로 인정합니다.

kimls7637 1년 전 0

2751번 문제 병합 정렬로 풀어보고 싶어서

인터넷 뒤져가며 열심히 코드를 써보았는데

시간 초과라고 뜨네요!

무엇이 문제인지 알려주시는 분 무적으로 인정합니다!

#include <stdio.h>

int newarray[1000000];

void calculation(int arr[], int first, int middle, int end)
{
    int i = first;
    int j = middle + 1;
    int k = first;
    while(i <= middle && j <= end)
    {
        if(arr[i] > arr[j])
        {
            newarray[k] = arr[j++];
        }
        else
        {
            newarray[k] = arr[i++];
        }
        k++;
    }
    if(i > middle)
    {
        for(int l = j; l <= end; l++)
        {
            newarray[k++] = arr[l];
        }
    }
    else
    {
        for (int l = i; l <= middle; l++)
        {
            newarray[k++] = arr[l];
        }
    }
    for (int l = 0; l <= end; l++)
    {
        arr[l] = newarray[l];
    }
}

void devide(int arr[], int first, int end)
{
    if (first < end)
    {
        int middle = (first + end) / 2;
        devide(arr, first, middle);
        devide(arr, middle + 1, end);
        calculation(arr, first, middle, end);
    }
}

int main(void)
{
    int n;
    int array[1000000];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &array[i]);
    }
  
    devide(array, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%d\n", newarray[i]);
    }

    return 0;
}

djm03178 1년 전 2

36~39번째 줄이 비효율적입니다. first부터 end까지만 복사하면 됩니다.

kimls7637 1년 전 0

와! 역시 멋지십니다!! 0을 first로 바꿔보았더니 시간 초과가 안 뜨네요!

근데 숫자를 하나만 입력할 때 제대로 출력 되지 않아서 틀렸습니다 라고 나오더라구요!

그래서 62번째 줄에 그냥

if(n == 1)
{
printf("%d", array[0]);
return 0;
}

를 박았더니 맞았습니다!! 라고 나오더라구요 !!!!!

역시 엄청나십니다

이 문제 해결 못하면 코딩 접으려 했는데

열심히해서 꼭 카카오 입사하겠습니다

나중에 밥 한 끼 사드리겠습니다

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

문제

문제

출처

ICPC

이거 해결하시는 분 무적으로 인정합니다.

kimls7637 1년 전 0

djm03178 1년 전 2

kimls7637 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말