[백준 2751] 정렬하기 2

1. 문제

https://www.acmicpc.net/problem/2751

 

 

 

2. Merge Sort 사용 구현

 

C 소스코드

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000000
 
    int sortArr[MAX];
 
//전역 변수로 하니까 바로되네 ㅅㅂ
 
 
 
void Merge(int arr[], int left, int mid, int right){
 
    int leftIndex = left, rightIndex = mid+1;
    int k = left;
    int i;
    // 대체..?
    
    while(leftIndex <= mid && rightIndex <= right)
    {
        if(arr[leftIndex] < arr[rightIndex])
        {
            sortArr[k++] = arr[leftIndex];
            leftIndex++;
        }
        else
        {
            sortArr[k++] = arr[rightIndex];
            rightIndex++;
        }
    }
 
    if(leftIndex > mid)
    {
        while(rightIndex <= right)
        {
        sortArr[k++] = arr[rightIndex++];
        }
    }
    else
    {    
        while(leftIndex <= mid) 
        {
        sortArr[k++] = arr[leftIndex++];
        }
    }
    
    // i = left 이거 한글자가 i= 0 보다 훨..
    //속도 좌우함.
     
    for(i = left ; i <= right; i++)
    {
        arr[i] = sortArr[i];
    }
}
 
void MergeSort(int arr[], int left, int right){
 
    int mid = (left + right)/2;
    if(left < right)
    {
 
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        
        Merge(arr, left, mid, right);
        
    }
}
 
int main(void)
{
    int i;
    int N;
    scanf("%d", &N);
    int arr[N];
    for(i = 0 ; i< N; i++)
    {
        scanf("%d", &arr[i]);
    } 
    
    MergeSort(arr, 0, N-1);
    
    for(i = 0; i < N ; i++)
    printf("%d\n", arr[i]);
    
    return 0;
}

 

Merge Sort로 구현했음에도 2번이나 시간초과가 나서

왜그런가 했더니

 

알고보니

 

 
    for(i = left ; i <= right; i++)
    {
        arr[i] = sortArr[i];
    }
}

 

여기서 i = left가 아닌 i = 0으로 코드를 짰었다.

(완벽하지 못한 이해로 인해..)

 

Divide가 이미 이루어진 배열들의 index는

첫번째 요소만 0이고 나머지는 1, 2, 3, ~~~~~ 각기 다른 시작점 , 끝점 index를 갖는다

 

따라서 left로 초기화 해줘야하는데 0으로해서 말도안되는 시간초과가 떴던것이다..

 

구현하면서 재귀와 배열 index범위에 대한 정확성 중요성을 짚어봤다.