C# 코딩테스트 강좌, K번째 수 구하기

코딩 테스트에서 자주 출제되는 문제 유형인 ‘K번째 수 구하기’에 대한 자세한 설명과 문제 해결 방법을 소개합니다.

문제 설명

주어진 배열 arr와 정수 K가 있을 때, K번째로 작은 수를 찾아 반환하는 문제입니다. 배열은 0부터 시작하는 인덱스를 가지며, 같은 수가 여러 개 있을 경우, 여러 개의 K번째 수 중 하나를 반환할 수 있습니다.

예를 들어, 배열이 [7, 10, 4, 3, 20, 15]이고 K=3일 경우, 3번째로 작은 수는 7입니다.

입력 형식

입력으로는 다음과 같은 형식이 주어집니다:

  • 첫 번째 줄: 배열의 크기 N (1 <= N <= 10^6)
  • 두 번째 줄: N개의 정수 (배열의 원소는 -10^9 이상 10^9 이하)
  • 세 번째 줄: 정수 K (1 <= K <= N)

입력 예시


6
7 10 4 3 20 15
3

출력 형식

배열 내에서 K번째로 작은 수를 출력합니다.

출력 예시


7

문제 풀이 과정

1단계: 문제 이해

우리는 그러면 주어진 배열에서 K번째로 작은 수를 찾아야 합니다. 배열이 정렬되어 있지 않기 때문에, 정렬된 상태에서 K번째 원소의 값을 찾아야 합니다.

2단계: 알고리즘 선택

가장 직관적인 방법은 배열을 정렬한 후 K번째 원소를 반환하는 것입니다. 그러나 이 방법은 O(N log N) 시간 복잡도를 가집니다. 이를 최적화하기 위해 다양한 방법이 존재합니다:

  • Quickselect 알고리즘 (평균 O(N) 시간 복잡도)
  • Heap 자료구조를 이용한 방법

이번 강좌에서는 Quickselect 방법을 사용하겠습니다.

3단계: Quickselect 설명

Quickselect는 Quick Sort 알고리즘과 유사하며, 피벗(pivot)을 선택하여 왼쪽 부분과 오른쪽 부분으로 나뉘게 됩니다. 이때 K의 위치에 따라 결과를 도출합니다.

Quickselect의 과정

  1. 중간 피벗값을 선택합니다.
  2. 피벗보다 작거나 같은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다.
  3. K가 피벗 인덱스와 동등하면 피벗을 반환합니다.
  4. K가 피벗보다 작으면 왼쪽 부분에 대해 Quickselect를 재귀적으로 호출합니다.
  5. K가 피벗보다 크면 오른쪽 부분에 대해 Quickselect를 재귀적으로 호출합니다.

C# 코드 구현


using System;
using System.Linq;

class KthSmallest
{
    public static int QuickSelect(int[] arr, int left, int right, int k)
    {
        if (left == right) // 배열에 원소가 하나만 있을 경우
            return arr[left];

        Random random = new Random();
        int pivotIndex = left + random.Next(right - left);
        int pivot = arr[pivotIndex];

        // 피벗을 최우측으로 이동
        Swap(arr, pivotIndex, right);
        int storeIndex = left;

        for (int i = left; i < right; i++)
        {
            if (arr[i] < pivot)
            {
                Swap(arr, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(arr, storeIndex, right); // 피벗을 제자리에 놓음

        if (k == storeIndex) return arr[k];
        else if (k < storeIndex) return QuickSelect(arr, left, storeIndex - 1, k);
        else return QuickSelect(arr, storeIndex + 1, right, k);
    }

    private static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int K = int.Parse(Console.ReadLine()) - 1; // K를 0-based index로 변환

        int result = QuickSelect(arr, 0, N - 1, K);
        Console.WriteLine(result);
    }
}

코드 설명

위의 C# 코드는 Quickselect 알고리즘을 사용하여 K번째 수를 찾습니다:

  • QuickSelect 메소드: 배열에서 K번째 작은 수를 찾아 반환합니다.
  • Swap 메소드: 두 원소의 위치를 바꿉니다.
  • Main: 입력을 받고 실행합니다.

이 알고리즘은 평균적으로 O(N) 시간 복잡도를 가지며, 이는 매우 효율적입니다.

마무리

이번 강좌에서는 C#을 사용하여 ‘K번째 수 구하기’ 문제를 해결하는 방법을 배웠습니다. Quickselect 알고리즘을 통해 효율적으로 문제를 해결하는 방법을 실습함으로써, 코딩 테스트에서 유용한 기법을 익힐 수 있었습니다. 추가적으로 다양한 알고리즘과 문제를 경험하여 더욱 능력을 키우길 바랍니다.