C# 코딩테스트 강좌, 수 정렬하기 1

안녕하세요! 이번 포스팅에서는 C#을 사용하여 코딩 테스트에서 자주 접할 수 있는 문제 중 하나인 “수 정렬하기”를 다루어 보겠습니다. 본 강좌는 알고리즘 문제의 이해부터 해결 과정까지 자세히 설명하고, 최종적으로 C# 코드를 구현하는 방법까지 알아볼 것입니다.

문제 설명

주어진 수의 개수만큼 수를 입력받아, 그 수들을 오름차순으로 정렬하여 출력하는 문제입니다. 정렬 알고리즘의 기초와 함께 다양한 방법으로 문제를 해결해보겠습니다.

문제 입력

첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 수가 주어집니다. 각 수는 절대값이 1,000,000보다 작거나 같은 정수입니다.

문제 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬된 결과를 출력합니다.

예제

문제 해결 과정

이 문제는 단순히 주어진 수들을 정렬하는 문제로, 여러 가지 정렬 알고리즘을 사용할 수 있습니다. 이 글에서는 기본적인 정렬 알고리즘 중 하나인 “병합 정렬(Merge Sort)”과 “C#의 내장 정렬 메서드”를 사용하여 문제를 해결하는 방법을 설명하겠습니다.

1. 병합 정렬(Merge Sort)

병합 정렬은 분할 정복(divide and conquer) 알고리즘의 일종으로, 주어진 배열을 반으로 나누어 각각을 정렬한 후, 다시 합쳐서 정렬하는 방식입니다. 평균 경우와 최악의 경우 모두 O(N log N)의 시간 복잡도를 가지며, 안정적인 정렬 방법입니다.

병합 정렬 절차

배열이 하나의 원소로 나눌 때까지 재귀적으로 배열을 나눈다.
나눈 배열을 정렬하며 합친다.

병합 정렬 구현

이제 C#으로 병합 정렬을 구현해 보겠습니다.


public class MergeSort
{
    public static void Sort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            // Divide the array elements
            Sort(array, left, mid);
            Sort(array, mid + 1, right);

            // Merge the sorted halves
            Merge(array, left, mid, right);
        }
    }

    public static void Merge(int[] array, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArray[i] = array[left + i];

        for (int j = 0; j < n2; j++)
            rightArray[j] = array[mid + 1 + j];

        int k = left, l = 0, m = 0;

        while (l < n1 && m < n2)
        {
            if (leftArray[l] <= rightArray[m])
            {
                array[k] = leftArray[l];
                l++;
            }
            else
            {
                array[k] = rightArray[m];
                m++;
            }
            k++;
        }

        while (l < n1)
        {
            array[k] = leftArray[l];
            l++;
            k++;
        }

        while (m < n2)
        {
            array[k] = rightArray[m];
            m++;
            k++;
        }
    }
}

2. C# 내장 정렬 메서드 사용하기

C#에서는 내장된 정렬 메서드를 사용하면 더 간단하게 문제를 해결할 수 있습니다.


using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] numbers = new int[n];

        for (int i = 0; i < n; i++)
        {
            numbers[i] = int.Parse(Console.ReadLine());
        }

        Array.Sort(numbers);

        foreach (var num in numbers)
        {
            Console.WriteLine(num);
        }
    }
}

분석 및 마무리

이 문제는 정렬의 기초를 배울 수 있는 좋은 기회입니다. 병합 정렬과 C#의 내장 메서드를 통해 어떻게 정렬이 이루어지는지, 그리고 어떤 방법이 더 효율적인지를 알 수 있었습니다. 코딩 테스트에서 자주 접할 수 있는 문제 형태이므로 자주 연습하는 것이 좋습니다.

다음 포스팅에서는 더 복잡한 정렬 문제나 알고리즘을 다룰 예정입니다. 함께 공부하면서 코딩 테스터로서의 능력을 키워나가길 바랍니다!