[BAEKJOON] 백준 24091: 알고리즘 수업 - 퀵 정렬 2 (C#)

문제 링크

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

 

 

문제

오늘도 서준이는 퀵 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 퀵 정렬로 배열 A를 오름차순 정렬할 경우 배열 A의 원소가 K 번 교환된 직후의 배열 A를 출력해 보자.

크기가 N인 배열에 대한 퀵 정렬 의사 코드는 다음과 같다.

quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- partition(A, p, r);  # 분할
        quick_sort(A, p, q - 1);  # 왼쪽 부분 배열 정렬
        quick_sort(A, q + 1, r);  # 오른쪽 부분 배열 정렬
    }
}

partition(A[], p, r) {
    x <- A[r];    # 기준원소
    i <- p - 1;   # i는 x보다 작거나 작은 원소들의 끝지점
    for j <- p to r - 1  # j는 아직 정해지지 않은 원소들의 시작 지점
        if (A[j] ≤ x) then A[++i] <-> A[j]; # i값 증가 후 A[i] <-> A[j] 교환
    if (i + 1 != r) then A[i + 1] <-> A[r]; # i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
    return i + 1;
}

 

 

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ 10^8)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 10^9)

 

 

출력

배열 A에 K 번 교환이 발생한 직후의 배열 A를 한 줄에 출력한다. 교환 횟수가 K 보다 작으면 -1을 출력한다.

 

 

 

통과한 답안

namespace _24091
{
    internal class Program
    {
        static int cnt = 0;
        static int K = 0;
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]);
            K = int.Parse(inputs[1]);
            int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            QuickSortAlgorithm(arr, 0, N - 1);

            if (cnt < K)
            {
                Console.WriteLine(-1);
            }

        }

        static void QuickSortAlgorithm(int[] arr, int p, int r)
        {
            if (p < r)
            {
                int q = Partition(arr, p, r);
                QuickSortAlgorithm(arr, p, q - 1);
                QuickSortAlgorithm(arr, q + 1, r);
            }
        }

        static int Partition(int[] arr, int p, int r)
        {
            int x = arr[r];
            int i = p - 1;

            for (int j = p; j < r; j++)
            {
                if (arr[j] <= x)
                {
                    i++;
                    Swap(arr, i, j);
                }
            }
            if (i + 1 != r)
            {
                Swap(arr, i + 1, r);
            }

            return i + 1;
        }

        static void Swap(int[] arr, int i , int j)
        {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;

            cnt++;
            if (cnt == K)
            {
                Console.WriteLine(String.Join(" ", arr));
            }
        }
    }
}

 

퀵 정렬의 기본을 알아보는 문제로

퀵 정렬은 주어진 자료에서 기준점을 잡고 그 값을 기준으로 다른 요소들과 비교하여

기준점보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬한다.

이후에 이 기준점을 기준으로 왼쪽과 오른쪽의 두 블록으로 나눈다.

이 과정이 퀵 정렬이 1회 진행되는 과정인데,

이를 더이상 분할할 수 없을 때까지 진행한다.

 

위의 코드를 가지고 설명하면,

static void QuickSortAlgorithm(int[] arr, int p, int r)
{
    if (p < r)
    {
        int q = Partition(arr, p, r);
        QuickSortAlgorithm(arr, p, q - 1);
        QuickSortAlgorithm(arr, q + 1, r);
    }
}

 

QuickSortAlgorithm이라는 메서드를 구현하여 퀵 정렬을 구현하였으며,

배열의 첫 부분이 p, 끝 부분이 r, 기준점을 q로 잡고 정렬을 진행하도록 구현하였다.

위의 코드에서 알 수 있듯이 q를 기준으로 잡고

p ~ q -1까지 한 블록으로, q + 1 ~ r까지 한 블록으로 나눠 두 블록으로 나눠서 퀵 정렬을 진행한다.

 

static int Partition(int[] arr, int p, int r)
{
    int x = arr[r];
    int i = p - 1;

    for (int j = p; j < r; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            Swap(arr, i, j);
        }
    }
    if (i + 1 != r)
    {
        Swap(arr, i + 1, r);
    }

    return i + 1;
}

 

분할하는 과정을 좀 더 자세히 살펴보면,

주어진 배열의 마지막 요소 arr[r]을 기준값으로 설정한 뒤에 포인터 i를 설정한다.

i는 기준값보다 작은 값들이 모일 공간을 가리키는 포인터이다.

 

이후에 for문을 통해서 기준값을 제외한 모든 요소들에 대해서

각 요소가 기준값보다 같거나 작다면 포인터 i의 크기를 증가시키고

arr[i]와 arr[j]를 교환하여 왼쪽으로 정렬되도록 한다.

 

마지막으로 i + 1과 r이 다른 경우에는 arr[i + 1]과 arr[r]을 교환하여

i + 1의 최종 위치를 반환한다.

 

간단히 설명하면, 주어진 배열에서 마지막에 있는 값을 기준값으로 잡은 뒤에

이 기준값보다 작다면 왼쪽으로, 크다면 오른쪽으로 위치를 변경하여

기준값이 배열에서 자신의 위치를 찾을 수 있도록 해주는 메서드이다.

 

이 과정에서 Swap 메서드를 이용하였는데,

간단하게 배열에서 두 요소의 위치를 교환하고,

교환했다는 카운트를 1 늘리는 메서드이다.

 

위의 두 메서드 QuickSortAlgorithm과 Partition을 통하여

각 단계마다 하나의 기준점(각 배열에서 마지막에 있는 요소)을 잡고

그 기준값이 중심에 오도록 정렬을 한 후에 분할하는 과정을 반복하도록 구현하였다.

 

이를 통하여 QuickSortAlgorithm이 1회 진행될 때마다

주어진 배열이 두 블록으로 나뉘고, 하나의 값이 자신의 위치를 찾게된다.

이를 계속 반복하여 배열의 각 요소들이 자신의 올바른 위치를 찾게 만드는 것이

퀵 정렬의 기본이라고 할 수 있다.