문제 이해하기
먼저 다음과 같은 정수 배열이 있다고 가정해 보겠습니다.
const arr = [4, 3, 4, 7, 5, 2, 3, 4, 3, 2, 3, 4];
이 배열의 각 요소를 y축 값으로 표현하고, 인접한 요소들은 x축에서 단위 거리만큼 떨어진 점으로 배치하면 아래와 같은 그래프가 그려집니다.
그래프를 살펴보면 이 배열에는 두 개의 피크(국소 최댓값)가 존재함을 알 수 있습니다. 하나는 인덱스 3에 있는 값 7, 다른 하나는 인덱스 7에 있는 값 4입니다.
문제 정의
우리가 작성해야 할 것은 정수 배열 arr을 첫 번째이자 유일한 인수로 받는 자바스크립트 함수입니다.
이 함수는 다음 두 가지 속성을 가진 객체를 반환해야 합니다.
- maximas: 배열에서 발견된 모든 피크의 값을 담은 배열
- positions: 각 피크에 해당하는 인덱스를 담은 배열
예를 들어 위 배열을 입력으로 넣으면 결과는 다음과 같아야 합니다.
const output = {
maximas: [7, 4],
positions: [3, 7]
};구현 코드
다음은 위 문제를 해결하는 전체 코드입니다.
const arr = [4, 3, 4, 7, 5, 2, 3, 4, 3, 2, 3, 4];
const findMaxima = (arr = []) => {
let positions = [];
let maximas = [];
for (let i = 1; i < arr.length - 1; i++) {
// 현재 요소가 이전 요소보다 큰 경우
if (arr[i] > arr[i - 1]) {
// 다음 요소보다도 크면 피크 확정
if (arr[i] > arr[i + 1]) {
positions.push(i);
maximas.push(arr[i]);
} else if (arr[i] === arr[i + 1]) {
// 연속된 같은 값(플래토) 처리
let temp = i;
while (arr[i] === arr[temp]) i++;
if (arr[temp] > arr[i]) {
positions.push(temp);
maximas.push(arr[temp]);
}
}
}
}
return { maximas, positions };
};
console.log(findMaxima(arr));코드 동작 원리
이 알고리즘의 핵심 로직은 다음과 같습니다.
- 탐색 범위 설정: 첫 번째와 마지막 요소는 양쪽 이웃이 없으므로 비교 대상에서 제외하고, 인덱스 1부터
length - 2까지만 순회합니다. - 오름 조건 확인: 현재 요소가 바로 앞 요소보다 클 때만 피크 가능성을 검사합니다. 즉, 상승 구간에 있어야 합니다.
- 하강 조건 확인: 상승 중인 요소가 바로 뒤 요소보다도 크면 상승 후 하강하는 지점, 즉 피크입니다.
- 플래토(평지) 처리: 현재 요소와 다음 요소가 같은 값을 가지면 임시 변수를 활용해 동일한 값이 끝나는 지점까지 이동한 뒤, 그 지점 이후 값이 더 작은지 확인하여 피크 여부를 판단합니다.
이 방식은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 매우 효율적입니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
{ maximas: [ 7, 4 ], positions: [ 3, 7 ] }결과에서 확인할 수 있듯이, 값 7은 인덱스 3에, 값 4는 인덱스 7에 위치한 피크로 정확하게 탐지되었습니다.