[C++ 알고리즘] 백준 2751번 : 수 정렬하기 2

 


Sort

수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이과정

1. 사용한 정렬 알고리즘

처음 구현할 때에는 퀵정렬 을 이용해 구현하였으나 퀵정렬 은 최악의 경우 시간 복잡도가 \(O(n^2)\)으로 백준에 제출하니 시간 초과가 나왔다. 구글링해보니 퀵정렬 은 최악의 경우 시간 복잡도가 좋지 않은 정렬 알고리즘이니 알고리즘 문제를 풀 때에는 웬만하면 사용하지 말라고 한다.
따라서 최악의 경우에도 시간 복잡도가 \(O(nlog_2 n)\)인 병합 정렬 을 통해 문제를 해결하였다.

:bulb: 참고 : [알고리즘] 퀵 정렬, 병합 정렬, 힙 정렬

2. 입출력 시

시간이 2초로 제한되어있어 입출력에도 이슈가 발생하리라 생각하여 여러 입출력 함수를 비교해보았다.

  • cin, cout 이용 시 : 716ms
  • scanf, printf 이용 시 : 432ms
  • cin.tie(NULL); ios::sync_with_stdio(false); 이용 시 : 320ms

cin.tie(NULL); ios::sync_with_stdio(false); 을 이용할 경우 cin, cout를 이용한 것보다 약 2배 빨라진 것을 볼 수 있다.

코드

#include <iostream>
#define _CRT_SECURE_NO_WARNINGS

using namespace std;

void merge(int* arr, int* sortedArr, int begin, int middle, int end) {
    int sortedInd = begin;
    int i = begin;
    int j = middle+1;


    while (i <= middle && j <= end) {
        if (arr[i] < arr[j]) sortedArr[sortedInd] = arr[i++];
        else  sortedArr[sortedInd] = arr[j++];

        sortedInd++;
    }

    //왼쪽이 오른쪽보다 모두 작은 경우
    if (i > middle) {
        while (j <= end) {
            sortedArr[sortedInd++] = arr[j++];
        }
    }
    //오른쪽이 왼쪽보다 모두 작은 경우
    if (j > end) {
        while (i <= middle) {
            sortedArr[sortedInd++] = arr[i++];
        }
    }

    for (int k = begin; k <= end; k++) arr[k] = sortedArr[k];

}

void mergeSort(int* arr, int* sortedArr, int begin, int end) {
    int middle;
    if (begin<end) {
        middle = (begin + end) / 2;
        mergeSort(arr, sortedArr, begin, middle);
        mergeSort(arr, sortedArr, middle + 1, end);
        merge(arr, sortedArr, begin, middle, end);
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;

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

    int* sortedArr = new int[n];
    mergeSort(arr, sortedArr, 0, n-1);

    for (int i = 0; i < n; i++)
        cout << arr[i] << '\n';

    return 0;
}

결과

image