[백준] 2751번: 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

nlogn의 시간복잡도를 가지는 알고리즘으로 정렬해야 해서 열심히 merge sort를 구현했는데,

자꾸 시간 초과가 뜬다. 

 

ios_base::sync_with_stdio(false);
cin.tie(0);

 

이거 두 개 사용해도 시간초과고, printf, scanf를 사용해도 시간초과다.

결국 merge sort에 문제가 있는 것 같은데, 검색해보니까 나랑 거의 비슷하게 merge sort를 구현한 사람들은 통과됐는데 나는 왜 안되지?

 

그리고 검색하다보니 quick sort로도 된다고 하는 사람들이 많았고,, (나는 최악의 경우에 nlogn이 안나올까봐 사용안했는데) 퀵소트를 이용할 거면 C++ 에 sort를 사용하면 되기 때문에...

 

어디서 읽은 바로는 c++에 sort는 퀵소트인데, 최악의 경우에도 nlogn을 보장한다고 한다.

 

암튼 그냥 sort 사용하니까 충격적이게도 됐다.

#include <iostream>
#include <algorithm>

int main(void) {

    int n;
    std::cin >> n;

    int* arr = new int[n];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    std::sort(arr, arr+n);

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

 

나중에 보고 다시 분석하라고 merge sort 시간 초과 뜬 것도 함께 첨부한다. 

#include <stdio.h>

using namespace std;

void merge(int arr[], int ans[], int start, int mid, int end) {

    //printf("merge: %d %d %d\n", start, mid, end);

    int i = start;
    int j = mid + 1;
    int k = start;
    
    // 오름차순 정렬
    while(i<=mid && j<=end){
        if (arr[i] <= arr[j]) {
            ans[k] = arr[i];
            //printf("ans[%d] = arr[%d] = %d\n", k, i, arr[i]);
            i++;
        }
        else {
            ans[k] = arr[j];
            //printf("ans[%d] = arr[%d] = %d\n", k, j, arr[j]);
            j++;
        }
        k++;
    }

    // 어느 한 쪽이 끝에 닿았다.
    if (i > mid) {
        // 앞 부분이 먼저 다 들어감
        for (; j <= end; j++, k++) {
            ans[k] = arr[j];
            //printf("ans[%d] = arr[%d] = %d\n", k, t, arr[t]);
        }
    }
    else {
        for (; i <= mid; i++, k++) {
            ans[k] = arr[i];
            //printf("ans[%d] = arr[%d] = %d\n", k, t, arr[t]);
        }
    }

    for (int i = 0; i <= end; i++) {
        arr[i] = ans[i];
    }
}

void mergeSort(int arr[], int ans[], int start, int end) {

    //printf("mergeSort: %d %d\n", start, end);

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

int main(void) {
    /*
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    */
    int n;
    scanf("%d", &n);

    int* arr = new int[n];
    int* ans = new int[n];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    mergeSort(arr, ans, 0, n-1);

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