본문 바로가기

Coding/BaekJoon

B_2751

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

 

2751번: 수 정렬하기 2

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

www.acmicpc.net

#include <iostream>
#include <vector>

using namespace std;

int N, arr[1000001];
int *sorted;

void merge(int left, int right)
{
    int mid = (left + right) / 2;
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            sorted[k++] = arr[i++];
        else
            sorted[k++] = arr[j++];
    }

    int temp = i > mid ? j : i;

    while (k <= right)
        sorted[k++] = arr[temp++];
    for (int i = left; i <= right; i++)
        arr[i] = sorted[i];
}

void partition(int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        partition(left, mid);
        partition(mid + 1, right);
        merge(left, right);
    }
}

int main()
{
    int N;
    cin >> N;
    sorted = new int[N];

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

    partition(0, N - 1);

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

'Coding > BaekJoon' 카테고리의 다른 글

B_24267  (0) 2023.09.26
B_10814  (0) 2023.09.26
B_18870  (0) 2023.09.26
B_2869  (0) 2023.09.26
B_1193  (0) 2023.09.26