배열에서 K번째로 큰 요소 찾기 – 정렬 기반 알고리즘과 C++ 구현

이 알고리즘은 주어진 데이터 집합에서 가장 큰 요소부터 K번째로 큰 요소까지를 찾아내는 방법입니다.

이 문제는 배열을 정렬하는 것만으로도 쉽게 해결할 수 있습니다. 배열을 오름차순 또는 내림차순으로 정렬할 수 있는데, 내림차순으로 정렬하면 앞쪽의 K개 요소가 곧바로 원하는 결과가 됩니다.

입력과 출력

입력:
배열의 요소: {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21}, K = 4

출력:
가장 큰 4개의 요소는 87 63 50 45

알고리즘

kthLargestElement(array, n, k)

입력: 배열, 배열의 요소 개수 n, 순위 k

출력: 배열에서 가장 큰 요소부터 K번째로 큰 요소까지 화면에 표시합니다.

Begin
   배열을 내림차순으로 정렬한다
   for i := 0 to k-1, do
      array[i]를 출력한다
   done
End

C++ 예제 코드

#include<iostream>
#include<algorithm>
using namespace std;

bool compare(int a, int b) {
   return a>b;
}

void kthLargestElement(int array[], int n, int k) {
   sort(array, array+n, compare);

   for (int i = 0; i < k; i++)    // 가장 큰 요소부터 K번째로 큰 요소까지
      cout << array[i] << " ";
}

int main() {
   int array[] = {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21};
   int n = 12;
   int k = 4;
   kthLargestElement(array, n, k);
}

실행 결과

87 63 50 45

시간 복잡도 분석

위 코드는 std::sort를 사용해 배열 전체를 정렬한 뒤 앞의 K개 요소만 출력하므로, 시간 복잡도는 O(n log n)입니다.

배열의 크기가 매우 크고 K가 작다면, 최대 힙(max-heap)을 이용해 상위 K개 요소만 유지하는 방식(O(n log k))이나 퀵셀렉트(Quickselect) 기법(평균 O(n))을 활용하면 더 효율적으로 문제를 해결할 수 있습니다.