글 읽기 - merge sort 시간초과

yonggi11 5년 전 0

merge sort를 구현하였지만 시간초과가 됐습니다. 어느 부분이 문제인지 알고 싶습니다.

#include <iostream>

using namespace std;

void merge(int* arr, int first_index, int second_index, int end){
    int arr_index = first_index;
    int first_limit = second_index-1;
    int arr_length = end-first_index+1;
    int* temp = new int[arr_length];
    int temp_index = 0;
    
    while((first_index <= first_limit) && (second_index <= end)){
        if(arr[first_index] < arr[second_index]) temp[temp_index++] = arr[first_index++];
        else temp[temp_index++] = arr[second_index++];
    }

    while(first_index <= first_limit) temp[temp_index++] = arr[first_index++];
    while(second_index <= end) temp[temp_index++] = arr[second_index++];

    for(int i =0; i < arr_length; i++) arr[arr_index++] = temp[i];
}

void mergeSort(int* arr, int start, int end){

    if(start < end){
        int middle = (start+end) / 2;
        mergeSort(arr, start, middle);
        mergeSort(arr, middle+1, end);
        merge(arr, start, middle+1, end);
    }
}

int main(){

    int n;

    cin >> n;

    int* arr = new int[n];

    for(int i=0; i<n; i++) cin >> arr[i];

    mergeSort(arr, 0, n-1);

    for(int i=0; i<n; i++) cout << arr[i] << endl;
}

djm03178 5년 전 0

https://www.acmicpc.net/proble...

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

문제

문제

출처

ICPC

merge sort 시간초과

yonggi11 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말