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

문제 주소는 여기로

 

앞의 정렬 문제 글에 이어서

포커스를 각기 맞춘 sorting algorithm에 대한 문제를 풀어 봤어요.

 

백준에는 총 3개의 sorting 관련 문제가 있는데,

1번은 메모리와 시간이 평범하며 입력하는 테스트 케이스의 수가 적은, 가장 보편적인 sorting 문제.

이것은 selection sort 로 풀었습니다.

3번은 메모리가 아주 제약되지만 시간이 넉넉한 sorting 문제.

이것은 counting sort로 풀었구요.

 

그리고 이번에 다룬 2번은 메모리는 넉넉하지만 입력 case가 많고, 시간이 2초로 상당히 빠듯한 sorting 문제입니다.

 

실제로 저도 2번 시도때는 전부 시간 초과가 걸렸었어요.

 

그래서 연산시간이 빠른 알고리즘을 찾아 봤습니다.

Merge sort, 또는 합병 정렬, 의 경우, O(n log n)의 시간 복잡도를 가지고, 특히 데이터의 크기가 클수록 효과적이라고 합니다.

이번 문제의 경우 입력되는 원소는 최대 100만 개, 원소의 범위도 절댓값이 100만 이하입니다. 이 정도면 데이터가 크다고 할 수 있겠죠.

따라서 merge sort로 접근하는 방법이 옳다고 생각하여 구현하였습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

void merge(int* numbers, int* sorted_array, int first, int end)
{
    int mid = (first+end)/2;
    int i = first;                      //앞의 배열을 가리킬 변수
    int j = mid+1;                      //뒤의 배열을 가리킬 변수
    int k = first;                      //임시 배열을 가리킬 변수
    
    while (i <= mid && j <= end)
    {
        if (numbers[i] <= numbers[j])
            sorted_array[k++] = numbers[i++];
        else
            sorted_array[k++] = numbers[j++];
        //나눠진 두 배열을 합치는 과정에서, 맨 앞의 값이 더 작은 쪽을 임시배열에 복사하고 가리키는 i/j, k 값을 각각 1 증가
    }
    //위 while문은 합치고자 하는 두 배열의 끝까지 전부 읽은 후 종료된다.
    
    int tmp= i > mid ? j : i;
    //i가 mid보다 크다면 j, 그렇지 않다면 i를 tmp 값으로 저장
    
    while (k <= end)
        sorted_array[k++] = numbers[tmp++];
    //이 부분은 저도 인터넷에서 보면서 잘 이해를 못 했어요. 어떤 의미의 코드인지 알려주시면 감사하겠습니다.
    
    for (int i = first; i <= end; i++)
        numbers[i] = sorted_array[i];
    //임시 배열에 담아둔 정렬된 값을 본 배열로 복사한다.
    
}

void merge_sort(int* numbers, int* sorted_array, int first, int end)
{
    int mid;
    
    if (first < end)
    {
        mid = (first+end)/2;
        merge_sort(numbers, sorted_array, first, mid);  //왼쪽 절반
        merge_sort(numbers, sorted_array, mid+1, end);  //오른쪽 절반
        merge(numbers, sorted_array, first, end);       //둘을 정렬하여 합치기
    }
}

int main()
{
    ios::sync_with_stdio(false);
    
    int elements;
    cin >> elements;
    
    int numbers[elements];
    int sorted_array[elements];
    
    for (int i = 0; i < elements; i++)
        cin >> numbers[i];
    
    merge_sort(numbers, sorted_array, 0, elements-1);
    
    for (int i = 0; i < elements; i++)
        cout << numbers[i] << '\n';
    
    return 0;
    
}

Merge sort는 divide and conquer 기법의 대표적인 알고리즘입니다.

주어진 문제, 즉 큰 문제를 해결하기 위해,

작은 요소요소로 나누어 먼저 해결하고,

이후 해결한 작은 요소요소를 각각 다시 합쳐 큰 문제를 해결합니다.

 

코드에 보시듯 재귀함수 구조로 주어진 숫자의 배열을 각각 반으로 나누며,

이를 합치는 과정에서 숫자를 정렬합니다.

나뉜 배열의 크기가 0 또는 1이면 배열이 이미 정렬되었다고 가정하여 정렬을 수행하지 않습니다.

 

더 자세한 설명은 이 블로그의 글을 참고해 주세요.

저도 여기서 읽고 배워왔습니다 ㅎㅎ

 

위 코드대로 작성해서 정답 판정을 받았네요.

숫자 입력 배열과 임시 배열 모두 입력받아서 계속 함수에 매개변수로 넘겨 주는게 효율적인지는 잘 모르겠어요.

더 효율적으로 코드를 짤 수 있는 방법이 있다면 댓글로 알려주시면 감사하겠습니다.