C++로 정렬되지 않은 배열에서 k번째로 작은 원소 찾기

개요

이 튜토리얼에서는 정렬되지 않은 배열에서 k번째로 작은 숫자를 찾는 C++ 프로그램을 작성해 보겠습니다. 접근 방식은 매우 간단합니다. 배열을 오름차순으로 정렬한 후, 인덱스 k-1에 해당하는 값을 반환하면 됩니다.

문제 해결 단계

• 배열과 k값을 초기화합니다.
• sort 함수를 사용하여 배열을 오름차순으로 정렬합니다.
• 정렬된 배열에서 인덱스 k-1에 위치한 값을 반환합니다.

그럼 코드를 살펴보겠습니다.

예제 코드

#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[] = { 3, 5, 23, 4, 15, 16, 87, 99 }, k = 5;
    cout << findKthSmallestNumber(arr, 7, k) << endl;
    return 0;
}

출력 결과

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

16

동작 원리

예제에서 사용한 배열 {3, 5, 23, 4, 15, 16, 87, 99}를 오름차순으로 정렬하면 {3, 4, 5, 15, 16, 23, 87, 99}가 됩니다. k 값이 5이므로 인덱스 4에 위치한 5번째 원소인 16이 결과로 반환됩니다.

시간 복잡도

C++의 sort 함수는 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 따라서 이 알고리즘의 전체 시간 복잡도 역시 O(n log n)입니다. 만약 더 큰 입력에 대해 효율성이 필요하다면, 평균 O(n)의 성능을 내는 퀵셀렉트(Quickselect) 알고리즘이나 우선순위 큐(priority queue)를 활용하는 방법도 고려할 수 있습니다.

마무리

지금까지 정렬되지 않은 배열에서 k번째로 작은 원소를 찾는 가장 기본적인 방법을 알아보았습니다. 코드가 짧고 직관적이어서 코딩 테스트나 간단한 문제 해결에 유용하게 활용할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.