C++ 코딩테스트 강좌, 배열에서 K번째 수 찾기

오늘은 C++ 코딩 테스트에서 자주 출제되는 문제 중 하나인 “배열에서 K번째 수 찾기”에 대해 알아보겠습니다. 이 문제의 목적은 정렬된 배열에서 K번째로 작은 수를 찾는 것입니다. 예제를 통해 이 문제를 해결하는 방법을 단계별로 분석해 보겠습니다.

문제 설명

주어진 배열에서 K번째로 작은 수를 찾는 프로그램을 작성하시오. 배열의 원소는 서로 다르며, 1부터 N까지의 정수로 이루어진다고 가정합니다.

입력

첫 번째 줄에 배열의 크기 N과 K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ N)
두 번째 줄에는 N개의 정수가 주어진다.

출력

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

예제

입력 예시:

5 2
9 3 1 5 2

출력 예시:

문제 해결 전략

이 문제를 해결하기 위해 필요한 단계는 다음과 같습니다:

주어진 배열을 정렬합니다.
K-1(indexing from 0) 번째 원소를 찾습니다.
그 값을 출력합니다.

C++ 코드 구현

이제 주어진 문제를 해결하기 위해 C++ 코드를 구현해보겠습니다. C++에서 배열을 정렬하려면 std::sort 함수를 사용할 수 있습니다. 아래는 해당 알고리즘을 적용한 코드입니다:

#include 
#include 
#include 

int main() {
    int N, K;
    std::cin >> N >> K; // N과 K 입력 받기
    std::vector arr(N); // N 크기의 배열 생성

    for (int i = 0; i < N; ++i) {
        std::cin >> arr[i]; // 배열 원소 입력 받기
    }

    std::sort(arr.begin(), arr.end()); // 배열 정렬

    std::cout << arr[K - 1] << std::endl; // K번째 수 출력 (0-indexed)
    return 0;
}

코드 설명

위 코드는 다음과 같은 과정으로 작동합니다:

먼저, iostream, vector, algorithm 라이브러리를 포함시킵니다. 전자는 입력과 출력을 위해, 후자는 배열 정렬을 위해 필요합니다.
변수 N과 K를 선언하고, 사용자로부터 입력받습니다.
크기가 N인 정수형 벡터 arr를 생성하여 사용자로부터 배열의 원소를 입력받습니다.
std::sort 함수를 사용하여 벡터를 정렬합니다.
K번째로 작은 수를 출력합니다. 배열의 인덱스는 0부터 시작하므로 K - 1을 사용합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 주로 정렬 과정에서 발생합니다. C++의 std::sort는 평균적으로 O(N log N)의 시간 복잡도를 가지므로, 전체 알고리즘의 시간 복잡도는 O(N log N)입니다. 공간 복잡도는 입력 배열을 저장하는 데에 O(N)이 소요됩니다.

추가 문제

이와 같은 문제를 변형하여 다양한 난이도의 문제를 풀어볼 수 있습니다. 예를 들면:

중복된 원소가 존재하는 경우
K번째로 큰 수를 찾는 경우
부분 배열에서 K번째 수를 찾는 경우

각각의 경우에 대해 약간의 로직을 수정하면 쉽게 대응할 수 있음을 기억하세요.

마무리

이번 포스트에서는 배열에서 K번째 수를 찾는 방법에 대해 알아보았습니다. 문제 해결 과정과 C++ 구현을 통해, 기본적인 정렬 알고리즘과 배열 다루는 방법에 대해 배울 수 있었습니다. 다양한 변형 문제들을 통해 연습해보시길 권장합니다. 여러분의 코딩 테스트 준비에 도움이 되길 바랍니다!