문제 개요
이 문제에서는 n개의 양의 정수로 구성된 배열 arr[]가 주어집니다. 우리의 목표는 배열에서 바로 이전 요소와 다음 요소보다 모두 큰 요소를 찾아 출력하는 프로그램을 작성하는 것입니다.
조건 설명: 배열 내에서 다음 조건을 만족하는 요소를 찾아야 합니다. 즉, 어떤 요소 arr[i]가 자신보다 인덱스가 하나 앞선 요소(arr[i-1])보다 크고, 동시에 인덱스가 하나 뒤인 요소(arr[i+1])보다도 커야 합니다. 이러한 요소는 흔히 '국소 최댓값(local peak)'이라고 불립니다.
예제로 문제 이해하기
입력: arr[] = {3, 2, 5, 7, 3, 4, 5}
출력: 7
설명:
요소 7을 기준으로 살펴보면,
- 인덱스가 하나 앞인 요소: 5
- 인덱스가 하나 뒤인 요소: 3
현재 요소 7은 두 요소(5, 3)보다 모두 크므로 조건을 만족합니다.
해결 접근 방법
가장 간단한 해결 방법은 배열의 각 요소에 대해 위 조건을 일일이 검사하고, 조건을 만족하는 요소를 출력하는 것입니다.
구체적인 단계는 다음과 같습니다.
- 1단계: 배열을 인덱스 1부터 n-2까지 순회합니다. 첫 번째와 마지막 요소는 양쪽 이웃이 존재하지 않으므로 제외됩니다.
- 2단계: 각 요소 arr[i]에 대해 arr[i] > arr[i-1] && arr[i] > arr[i+1] 조건을 검사합니다.
- 3단계: 조건이 참이면 해당 요소 arr[i]를 출력합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
void findElementsInArray(int arr[], int n) {
for (int i = 1; i < n-1; i++)
if (arr[i] > arr[i+1] && arr[i] > arr[i-1]) {
cout << arr[i] << "\t";
}
}
int main()
{
int n = 7;
int arr[n] = { 5, 4, 7, 1, 17, 8, 3 };
cout << "조건을 만족하는 요소들: ";
findElementsInArray(arr, n);
return 0;
}
출력 결과
조건을 만족하는 요소들: 7 17
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 되므로 선형 시간 안에 처리할 수 있습니다.
- 공간 복잡도: O(1) — 추가적인 저장 공간 없이 상수 공간으로 해결할 수 있습니다.