C++로 구현하는 오른쪽에 있는 더 큰 요소(NGE) 개수 세기

배열과 특정 요소의 인덱스가 주어졌을 때, 그 요소의 오른쪽에 위치하면서 값이 더 큰 요소가 몇 개인지 세는 문제를 풀어보겠습니다. 이러한 요소는 흔히 NGE(Next Greater Element)라고 불립니다.

문제 예시

입력

arr = [2, 3, 5, 1, 4, 2, 6]
index = 3

출력

3

인덱스 3에 해당하는 대상 요소는 1입니다. 이 요소의 오른쪽에는 4, 2, 6 총 세 개의 요소가 있으며, 모두 1보다 큰 값입니다. 따라서 정답은 3이 됩니다.

알고리즘 접근 방법

이 문제는 단순한 선형 탐색으로 해결할 수 있습니다. 절차는 다음과 같습니다.

• 배열과 대상 요소의 인덱스를 초기화합니다.
• 인덱스가 배열의 길이보다 크거나 같으면 유효하지 않은 입력이므로 -1을 반환합니다.
• 주어진 인덱스의 다음 요소부터 배열 끝까지 반복문을 실행합니다.
  • 탐색 중인 요소가 대상 요소보다 크면 카운트를 1 증가시킵니다.
• 반복문이 끝나면 카운트를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 추가적인 공간은 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다.

C++ 구현

다음은 위에서 설명한 알고리즘을 C++로 구현한 코드입니다.

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

int getNextGreaterElementsCount(int arr[], int n, int index) {
    if (index >= n) {
        return -1;
    }
    int count = 0;
    for (int i = index + 1; i < n; i++) {
        if (arr[index] < arr[i]) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int n = 8, index = 1;
    cout << getNextGreaterElementsCount(arr, n, index) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

6

예제에서 대상 요소는 인덱스 1의 값 2입니다. 배열이 1부터 8까지 오름차순으로 정렬되어 있으므로, 2의 오른쪽에 있는 3, 4, 5, 6, 7, 8 여섯 개의 요소가 모두 2보다 큽니다. 따라서 결과값은 6이 출력됩니다.