C++로 배열에서 자신보다 큰 요소가 두 개 이상인 모든 원소 찾기

n개의 숫자로 이루어진 배열이 있다고 가정해 봅시다. 이때 배열 안에서 자신보다 큰 요소가 최소 두 개 이상 존재하는 모든 원소를 찾아야 합니다. 예를 들어 배열이 A = [2, 8, 7, 1, 5]라면 결과는 [2, 1, 5]가 됩니다. 2, 1, 5는 각각 8, 7처럼 자신보다 큰 값을 두 개 이상 가지고 있기 때문입니다.

문제 해결 접근 방법

이 문제는 정렬 없이도 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열을 한 번 순회하며 최댓값(first_max)과 두 번째로 큰 값(second_max)을 구합니다.
• 다시 배열을 순회하면서 second_max보다 작은 모든 요소를 출력합니다.

second_max보다 작은 요소라면 반드시 first_max와 second_max, 즉 두 개 이상의 더 큰 요소를 가지므로 조건을 만족합니다. 이 방법의 시간 복잡도는 O(n)으로, 배열을 정렬한 뒤 처리하는 O(n log n) 방식보다 효율적입니다.

예제 코드

#include<iostream>
using namespace std;
void searchElements(int arr[], int n) {
    int first_max = INT_MIN, second_max = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > first_max) {
            second_max = first_max;
            first_max = arr[i];
        } else if (arr[i] > second_max)
            second_max = arr[i];
    }
    for (int i = 0; i < n; i++)
        if (arr[i] < second_max)
            cout << arr[i] << " ";
}
int main() {
    int arr[] = { 2, 9, 1, 7, 5, 3, 17};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Elements are: ";
    searchElements(arr, n);
}

실행 결과

위 코드에서 최댓값은 17, 두 번째로 큰 값은 9이므로, 9보다 작은 요소들이 모두 출력됩니다.

Elements are: 2 1 7 5 3