C++ STL로 정렬되지 않은 배열에서 K번째 작은 수 찾는 방법

이 튜토리얼에서는 정렬되지 않은 배열에서 k번째로 작은 수를 찾는 프로그램을 C++의 STL(표준 템플릿 라이브러리)을 활용해 작성하는 방법을 알아보겠습니다.

STL의 set 컨테이너는 내부적으로 균형 이진 탐색 트리(레드-블랙 트리) 기반으로 구현되어 있어, 원소가 자동으로 오름차순으로 정렬되고 중복 없이 저장됩니다. 이러한 특성 덕분에 k번째 작은 수를 손쉽게 구할 수 있습니다.

문제 해결 단계

배열과 k값을 초기화합니다.
비어 있는 ordered set(정렬된 집합)을 하나 생성합니다.
배열을 순회하며 각 원소를 집합에 삽입합니다.
집합의 시작 지점부터 k - 1번째까지 반복자(iterator)를 이동시킵니다.
해당 위치의 값을 반환합니다.

예제 코드

전체 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int findKthSmallestNumber(int arr[], int n, int k) {
    set<int> s;
    for (int i = 0; i < n; i++) {
        s.insert(arr[i]);
    }
    auto it = s.begin();
    for (int i = 0; i < k - 1; i++) {
        it++;
    }
    return *it;
}

int main() {
    int arr[] = { 45, 32, 22, 23, 12 }, n = 5, k = 3;
    cout << findKthSmallestNumber(arr, n, k) << endl;
    return 0;
}

실행 결과

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

코드 동작 원리와 시간 복잡도

위 예제에서 배열 {45, 32, 22, 23, 12}의 모든 원소를 set에 삽입하면 자동으로 {12, 22, 23, 32, 45}처럼 정렬됩니다. 여기서 k = 3이므로 반복자를 두 번 이동시켜 세 번째 원소인 23을 반환하게 됩니다.

set에 원소를 한 번 삽입할 때 O(log n)의 시간이 걸리므로 전체 삽입 과정의 시간 복잡도는 O(n log n)이며, k번째 원소를 찾는 과정에는 O(k)가 추가로 소요됩니다.

마무리

이상으로 STL의 set을 활용해 k번째 작은 수를 찾는 방법을 살펴보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요!