C++로 정렬되지 않은 배열에서 k번째로 작은/큰 요소 찾는 방법

개요

이 튜토리얼에서는 정렬되지 않은 배열에서 k번째로 작은 숫자를 찾는 C++ 프로그램을 작성해 보겠습니다.

문제 해결 과정은 다음 단계로 진행됩니다.

• 배열과 k 값을 초기화합니다.
• sort 메서드를 사용하여 배열을 오름차순으로 정렬합니다.
• 인덱스 k - 1에 해당하는 배열 요소를 반환합니다.

배열을 오름차순으로 정렬하면 가장 작은 값부터 차례대로 배치되므로, k번째로 작은 값은 항상 인덱스 k - 1 위치에 있습니다. 반대로 k번째로 큰 값을 구하고 싶다면 인덱스 n - k 위치의 값을 반환하거나 내림차순으로 정렬하면 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int findKthSmallestNumber(int arr[], int n, int k) {
    sort(arr, arr + n);
    return arr[k - 1];
}
int main() {
    int arr[] = { 45, 32, 22, 23, 12 }, n = 5, k = 3;
    cout << findKthSmallestNumber(arr, n, k) << endl;
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

23

배열 { 45, 32, 22, 23, 12 }를 정렬하면 { 12, 22, 23, 32, 45 }가 되고, k = 3이므로 인덱스 2에 있는 값인 23, 즉 세 번째로 작은 숫자가 반환됩니다.

시간 복잡도

이 방법은 배열 전체를 정렬하기 때문에 시간 복잡도는 O(n log n)입니다. 데이터 크기가 크고 성능이 중요하다면 우선순위 큐(최소 힙) 또는 퀵 셀렉트(Quickselect) 알고리즘을 사용하면 평균적으로 더 효율적인 처리가 가능합니다.

마무리

지금까지 C++에서 정렬되지 않은 배열의 k번째로 작은 요소를 찾는 간단하고 직관적인 방법을 살펴보았습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.