C++로 주어진 배열의 국소 극값 개수 계산하기

길이가 n인 배열 A가 있다고 가정해 봅시다. 배열의 어떤 원소 A[i]가 양쪽 이웃한 원소보다 엄격하게 작으면 국소 최솟값(local minimum)이라고 부르고, 반대로 양쪽 이웃한 원소보다 엄격하게 크면 국소 최댓값(local maximum)이라고 부릅니다. 다만 첫 번째 원소 A[0]과 마지막 원소 A[n-1]은 이웃이 하나뿐이므로 극댓값이나 극솟값으로 간주하지 않습니다. 이 문제의 목표는 주어진 배열에서 이러한 국소 극값(local extrema)의 총 개수를 구하는 것입니다.

예를 들어 입력이 A = [1, 5, 2, 5]라면 출력은 2가 됩니다. A[1] 위치의 5는 국소 최댓값이고, A[2] 위치의 2는 국소 최솟값이기 때문입니다.

풀이 접근 방법

이 문제는 다음과 같은 단계로 해결할 수 있습니다.

결괏값을 저장할 변수 sum을 0으로 초기화합니다.
배열의 크기를 n에 저장합니다.
i를 1부터 n-2까지 순회하면서 각 원소가 양쪽 이웃보다 모두 작거나 모두 큰지 확인합니다.
조건을 만족하면 sum을 1씩 증가시킵니다.
순회가 끝나면 sum을 반환합니다.

sum := 0
n := size of A
for initialize i := 1, when i < n - 1, update (increase i by 1), do:
    if (A[i] < A[i - 1] and A[i] < A[i + 1]) or (A[i] > A[i + 1] and A[i] > A[i - 1]), then:
        (increase sum by 1)
return sum

예제 코드

아래 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 효율적으로 동작합니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
    int sum = 0;
    int n = A.size();
    for (int i = 1; i < n - 1; i++)
        if ((A[i] < A[i - 1] && A[i] < A[i + 1]) || (A[i] > A[i + 1] && A[i] > A[i - 1]))
            sum++;
    return sum;
}
int main(){
    vector<int> A = { 1, 5, 2, 5 };
    cout << solve(A) << endl;
}

입력

{ 1, 5, 2, 5 }