2751번 수 정렬하기2

#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define MAX 1000000
 
void merge(int arr[], int mid, int low, int high) {
    int temp[MAX];
 
    int i,j,k;
 
    for(i = low; i <= high; i++) 
        temp[i] = arr[i];
 
    i = k = low;
    j = mid + 1;
 
    while(i<=mid && j<=high) {
        if(temp[i] <= temp[j])
            arr[k++] = temp[i++];
        else 
            arr[k++] = temp[j++];
    }
 
    while(i <= mid)
        arr[k++] = temp[i++];
    while(j <= high)
        arr[k++] = temp[j++];
}
 
void mergeSort(int arr[], int low, int high) {
    int mid = (low + high) / 2;
 
    if(low == high) 
        return;
 
    mergeSort(arr,low, mid);
    mergeSort(arr, mid + 1, high);
    merge(arr, mid, low, high);
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    int arr[MAX];
 
    for(int i = 0; i < n; i++) 
        scanf("%d", &arr[i]);
    
    mergeSort(arr, 0, n - 1);
 
    for(int i = 0; i < n; i++)
        printf("%d\n", arr[i]);
 
    return 0;
}

이 문제는 앞의 2750번과 같은 문제이지만 mergesort나 heap정렬을 이용해서 풀어야 하는 문제이다.

그렇지 않으면 시간초과가 나온다고한다.

merge sort를 이용해서 문제를 풀었는데 merge sort의 기본개념은 정렬을 해주고 싶은 배열을 먼저 받는다.

그리고 그 배열을 계속해서 반으로 쪼개가면서 그 쪼갠 배열에서 정렬을 해주는 것이다. 계속해서 배열을 쪼개다가 마지막 한개가 남았을 경우에는 이미 정렬된 것으로 판단하고 함수 호출을 끝낸다. 이것이 mergeSort에 구현된 부분이다.

low와 high가 같다는 것은 배열에 인자가 하나뿐이라는 뜻이다.

그것이 아니라면 중간값인 mid를 구해서 반으로 쪼갠 왼쪽부분과 오른쪽부분을 따로 mergeSort를 실행해준다.

그리고 난 후에 쪼개져 있는 배열들을 합치는 merge함수를 실행해주는 것이다.

merge함수에서 일어나는 일에 대해 설명을 하면 먼저 임시로 값을 저장할 temp배열을 만든다. 이 배열을 만드는 이유는 반으로 나눠져 있는 배열의 순서를 알맞게 순서대로 맞춘다음 하나로 합치기 위함이다.

하나의 배열인 arr을 받아서 마치 두개인 것처럼 i와 j를 이용해서 차례대로 정렬될 수 있도록 arr에 저장을 해준다.

그리고 마지막으로 i나 j에 남아있는 값들이 모두 arr에 저장될 수 있도록 마지막 while문을 돌린다. 이 while문을 해주는 이유는 i값이 mid에 도달하지 못하였는데 끝났거나 j값이 high값에 도달하지 못하였는데 while(i <= mid && j <= high) 이 반복문이 끝났을 경우에 위함이다.