C++에서 배열의 최댓값 k개를 원래 순서대로 찾는 방법

문제 개요

이 문제에서는 n개의 요소로 구성된 배열 arr[]가 주어지며, 우리의 목표는 배열에서 가장 큰 k개의 요소를 원래 순서 그대로 찾아 출력하는 것입니다.

즉, 단순히 큰 값부터 정렬해서 출력하는 것이 아니라, 원본 배열에서의 인덱스 순서를 그대로 유지한 채 상위 k개의 최댓값을 출력해야 합니다.

예제로 이해하기

입력: arr[] = {5, 1, 3, 6, 2}, k = 2

출력: 5, 6

설명:

배열에서 가장 큰 두 요소는 6과 5입니다. 하지만 원래 배열에서는 5가 6보다 앞쪽 인덱스에 위치하므로, 그 순서를 유지하여 "5, 6"으로 출력합니다.

해결 접근 방법

이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.

1. 먼저 원본 배열 arr[]의 모든 요소를 복사한 배열 decArr을 만들고, 이를 내림차순으로 정렬합니다.
2. 그런 다음 원본 배열을 처음부터 끝까지 순회하면서, 현재 요소가 decArr의 앞부분(상위 k개)에 존재하는지 확인합니다.
3. 존재한다면 해당 요소는 최댓값 k개 중 하나이므로, 원래 순서대로 출력합니다.

이렇게 하면 값의 크기와 무관하게 원본 배열의 인덱스 순서를 자연스럽게 보존할 수 있습니다.

C++ 구현 예제

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

// 현재 요소가 상위 k개 값에 포함되어 있는지 확인하는 함수
bool searchVal(int decArr[], int k, int ele){
    for(int i = 0; i < k; i++){
        if( decArr[i] == ele)
            return true;
    }
    return false;
}

void printKMaxEle(int arr[], int k, int n) {
    
    // 원본 배열 복사 후 내림차순 정렬
    int decArr[n];
    for(int i = 0; i < n ; i++){
        decArr[i] = arr[i];
    }
    sort(decArr, decArr + n, greater<int>());

    // 원본 배열 순회하며 상위 k개에 해당하는 요소만 출력
    for (int i = 0; i < n; ++i)
        if ( searchVal(decArr, k, arr[i]) )
            cout<<arr[i]<<" ";
}

int main() {
    
    int arr[] = { 15, 1, 3, 6, 2, 34, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout<<k<<" maximum elements of the array in their original order are \n";
    printKMaxEle(arr, k, n);
    return 0;
}

실행 결과

3 maximum elements of the array in their original order are
15 34 9

시간 복잡도 분석

내림차순 정렬에는 O(n log n), 각 요소가 상위 k개에 속하는지 확인하는 작업은 최악의 경우 O(k)가 소요되므로, 전체 시간 복잡도는 O(n log n + n·k)입니다.

성능을 더 개선하고 싶다면 unordered_map 또는 unordered_set에 상위 k개 값을 미리 저장해 두면 포함 여부를 평균 O(1)에 확인할 수 있어, 전체 복잡도를 O(n log n)으로 줄일 수 있습니다.