C++에서 배열에서 가장 큰 3개의 요소 찾기

이 문제에서는 정렬되지 않은 N개의 요소로 구성된 배열 arr[]가 주어지며, 우리의 과제는 배열에서 가장 큰 세 개의 요소를 찾는 것입니다.

예시를 통해 문제를 이해해 보겠습니다,

입력 : arr[] = {7, 3, 9, 12, 1}
출력 : 12, 9, 7

해결 접근 방법

기본적으로 배열에서 가장 큰 세 개의 요소를 찾아 출력하면 됩니다. 이 작업은 여러 가지 방법으로 수행할 수 있습니다.

방법 1: 단일 순회를 이용한 탐색

가장 큰 세 개의 요소를 저장하기 위해 max, max2, max3라는 세 개의 변수를 만들고, 이 값들을 arr[0]으로 초기화합니다.

그다음 i → 1부터 n-1까지 반복문을 돌면서 각 요소에 대해 다음 조건을 검사합니다.

if (arr[i] > max) → max3 = max2, max2 = max, max = arr[i]

else if (arr[i] > max2) → max3 = max2, max2 = arr[i]

else if (arr[i] > max3) → max3 = arr[i]

반복문이 끝나면 세 개의 값을 모두 출력합니다. 이 방법은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다.

예제

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;
void findThreeLargestElements(int arr[], int arr_size){
    int max, max2, max3;
    max3 = max = max2 = arr[0];
    for(int i = 0; i < arr_size; i++){
        if (arr[i] > max){
            max3 = max2;
            max2 = max;
            max = arr[i];
        }
        else if (arr[i] > max2){
            max3 = max2;
            max2 = arr[i];
        }
        else if (arr[i] > max3)
            max3 = arr[i];
    }
    cout<<endl<<"배열에서 가장 큰 세 요소는 "<<max<<", "<<max2<<", "<<max3;
}
int main(){
    int arr[] = {15, 2, 7, 86, 0, 21, 50};
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout<<"배열 : ";
    for(int i = 0; i < n; i++) 
        cout<<arr[i]<<"\t"; 
    findThreeLargestElements(arr, n);
    return 0;
}

출력 결과

배열 : 15 2 7 86 0 21 50
배열에서 가장 큰 세 요소는 86, 50, 21

방법 2: 정렬을 이용한 탐색

문제를 해결하는 또 다른 방법은 배열을 정렬한 후, 가장 큰 세 개의 요소에 해당하는 앞쪽 세 개의 요소를 출력하는 것입니다. 다만 정렬에는 O(n log n)의 시간이 소요되므로, 배열의 크기가 클 경우 방법 1보다 비효율적일 수 있습니다.

알고리즘

1단계 − 정렬 기법을 사용하여 배열을 내림차순으로 정렬합니다.

2단계 − 첫 번째부터 세 번째 요소까지 출력합니다: arr[0], arr[1], arr[2]

참고로 아래 코드는 중복된 값을 건너뛰도록 처리하여, 서로 다른 세 개의 큰 값이 출력되도록 구현했습니다.

예제

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
void findThreeLargestElements(int arr[], int n){
    sort(arr, arr + n, std::greater<>());
    int j = 0;
    cout<<"\n가장 큰 세 요소는 ";
    for(int i = 0; i < n; i++){ 
        if(arr[i] != arr[i+1]){ 
            cout<<arr[i]<<" "; 
            j++;
        }
        if(j == 3){
            break;
        }
    }
}
int main(){
    int arr[] = {15, 2, 7, 86, 0, 21, 50, 53, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열 : ";
    for(int i = 0; i < n; i++)
        cout<<arr[i]<<"\t";
    findThreeLargestElements(arr, n);
    return 0;
}

출력 결과

배열 : 15 2 7 86 0 21 50 53 50
가장 큰 세 요소는 86 53 50