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

안녕하세요! 이번 글에서는 C++을 이용한 코딩테스트 문제 중 하나인 “K번째 수 구하기”에 대해 다뤄보겠습니다. 쿠폰 픽업과 같이 실생활에서도 한 번쯤은 고민해본 K번째 수 구하기 문제는 알고리즘 문제풀이에서 자주 접할 수 있는 문제 중 하나입니다. 이번 포스트에서는 문제 정의부터 풀이 과정, C++ 코드 구현까지 상세히 설명하겠습니다.

문제 정의

주어진 정수 배열이 있고, 이 배열에서 K번째로 작은 수를 찾는 문제입니다. 여기서 K는 1부터 시작하는 정수로, 첫 번째로 작은 수, 두 번째로 작은 수, …의 의미를 갖습니다.

예를 들어, 다음과 같은 입력을 고려해 봅시다:

배열: [3, 1, 2, 4, 5]
K: 3

주어진 배열에서 3번째로 작은 수는 3입니다. 따라서 이 경우의 정답은 3이 됩니다.

입력 형식

첫 번째 줄: 배열의 길이 N (1 <= N <= 100,000)
두 번째 줄: 정수 배열 A (1 <= A[i] <= 10^9)
세 번째 줄: 정수 K (1 <= K <= N)

출력 형식

K번째로 작은 수를 출력합니다.

문제 풀이 계획

이 문제를 해결하기 위해 사용할 수 있는 몇 가지 알고리즘을 생각해 볼 수 있습니다.

정렬: 배열을 정렬한 후 K번째 인덱스를 반환합니다.
최소힙 사용: 힙을 사용해서 K번째로 작은 수를 찾아낼 수 있습니다.
퀵 선택 알고리즘: 평균 O(N) 시간복잡도로 K번째 수를 찾을 수 있는 알고리즘입니다.

여기서는 가장 직관적이고 이해하기 쉬운 방법인 배열 정렬을 사용한 풀이를 구현해 보겠습니다.

구현하기

먼저 C++의 vector를 사용하여 배열을 입력받고, sort() 함수를 이용해 정렬하겠습니다. 그 후, K번째 수를 출력하는 방식으로 프로그램을 구성하겠습니다.

코드 구현

#include 
#include 
#include  // sort()의 사용을 위해 include
using namespace std;

int main() {
    int N, K;
    
    // 배열의 크기 N 입력
    cout << "배열의 길이 N을 입력하세요: ";
    cin >> N;

    vector A(N);
    
    // 배열 A 입력
    cout << "정수 배열 A를 입력하세요 (띄어쓰기로 구분): ";
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    // K 값 입력
    cout << "K 값을 입력하세요: ";
    cin >> K;

    // 배열 정렬
    sort(A.begin(), A.end());

    // K번째 수 출력 (인덱스는 K-1)
    cout << K << "번째 수는: " << A[K - 1] << endl;

    return 0;
}

코드 설명

이 코드는 다음과 같은 흐름으로 동작합니다:

사용자로부터 배열의 길이 N을 입력받습니다.
N 길이의 정수 형 벡터 A를 생성합니다.
사용자로부터 배열 A의 원소를 입력받습니다.
K 값을 입력받습니다.
배열 A를 오름차순으로 정렬합니다.
K번째 수를 출력합니다. C++에서는 인덱스가 0부터 시작하므로 K-1을 사용해야 합니다.

코드 분석

문제의 입력은 최대 100,000개로, 최악의 경우 O(N log N)의 시간복잡도를 가진 정렬을 수행하게 됩니다. 정렬 후에는 K번째 수를 O(1) 시간에 찾을 수 있으므로, 전체 시간복잡도는 O(N log N)입니다. 이는 주어진 시간 제한 내에 충분히 해결할 수 있는 복잡도입니다.

테스트 케이스

위 코드를 검증하기 위해 몇 가지 테스트 케이스를 고려해 보겠습니다:

테스트 케이스 1

입력:
5
3 1 2 4 5
3
출력:
3번째 수는: 3

테스트 케이스 2

입력:
10
10 9 8 7 6 5 4 3 2 1
5
출력:
5번째 수는: 5

테스트 케이스 3

입력:
5
1 10000 500 999 1000
2
출력:
2번째 수는: 500

결과 및 최적화

기본적인 풀이를 구현해 보았습니다. 정렬을 사용한 방법은 직관적이며 구현이 용이하지만, 배열의 크기가 매우 클 경우 다른 방법이 필요할 수 있습니다. 예를 들어, 퀵 선택 알고리즘을 사용하는 방법이 있습니다. 퀵 선택 알고리즘은 평균적으로 O(N)의 성능을 가지며, 메모리가 제한된 경우 유용하게 사용될 수 있습니다.

퀵 선택 알고리즘 개요

퀵 선택 알고리즘은 분할 정복 알고리즘의 일종으로, 랜덤 피벗을 선택하여 배열을 두 부분으로 나누고 K번째 수가 어떤 부분에 있는지를 판별하여 해당 부분만 계속 찾는 방법입니다. 매우 큰 배열에서도 빠르게 K번째 수를 찾을 수 있습니다.

퀵 선택 구현 예시

#include <iostream>
#include <vector>
#include <cstdlib> // rand() 함수를 위해
using namespace std;

// 배열에서 K번째 수를 찾는 퀵 선택 알고리즘
int quickSelect(vector& A, int left, int right, int K) {
    if (left == right) return A[left];

    int pivotIndex = left + rand() % (right - left);
    int pivotValue = A[pivotIndex];

    // 피벗을 배열의 맨 끝으로 이동
    swap(A[pivotIndex], A[right]);
    int storeIndex = left;

    for (int i = left; i < right; i++) {
        if (A[i] < pivotValue) {
            swap(A[storeIndex], A[i]);
            storeIndex++;
        }
    }

    // 피벗을 자신의 위치로 이동
    swap(A[storeIndex], A[right]);

    if (K == storeIndex) return A[K];
    else if (K < storeIndex) return quickSelect(A, left, storeIndex - 1, K);
    else return quickSelect(A, storeIndex + 1, right, K);
}

int main() {
    int N, K;

    cout << "배열의 길이 N을 입력하세요: ";
    cin >> N;

    vector A(N);
    
    cout << "정수 배열 A를 입력하세요 (띄어쓰기로 구분): ";
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    cout << "K 값을 입력하세요: ";
    cin >> K;

    int result = quickSelect(A, 0, N - 1, K - 1);
    cout << K << "번째 수는: " << result << endl;

    return 0;
}

마무리

오늘은 C++을 이용하여 K번째 수를 찾는 문제를 해결하는 방법에 대해 알아보았습니다. 기본적인 방법으로는 배열을 정렬하여 K번째 수를 찾는 방법을 구현하였고, 더 효율적인 방법으로 퀵 선택 알고리즘에 대해서도 간략히 설명드렸습니다. 이러한 문제들은 코딩 테스트에서 자주 출제되므로 반복적으로 학습해 두는 것이 좋습니다. 이 문제를 통해 알고리즘의 기초적인 이해와 C++ 프로그래밍 능력을 키우는 데 도움이 되길 바랍니다.

독서 감사합니다! 추가적인 질문이 있으시면 댓글로 남겨주세요.