이번 글에서는 정수 배열을 입력받아, 배열 안에서 가장 길게 감소하는 연속 부분 수열의 길이를 반환하는 JavaScript 함수를 작성하는 방법을 알아보겠습니다.
문제 이해하기
함수는 정수로 이루어진 배열을 하나 받으며, 배열 내 요소들이 연속적으로 감소하는 구간 중 가장 긴 구간의 길이를 반환해야 합니다.
예를 들어, 입력 배열이 다음과 같다고 가정해 보겠습니다.
const arr = [5, 2, 5, 4, 3, 2, 4, 6, 7];
이 경우 기대되는 출력값은 다음과 같습니다.
const output = 4;
그 이유는 배열에서 [5, 4, 3, 2]가 가장 긴 감소 연속 수열이며, 그 길이가 4이기 때문입니다.
구현 코드
위 문제는 배열을 한 번만 순회하면서 현재까지의 감소 구간을 추적하는 방식으로 해결할 수 있습니다. 감소가 끊기는 지점에서 새로운 구간을 시작하고, 지금까지 발견한 최장 구간을 계속 갱신하면 됩니다.
const arr = [5, 2, 5, 4, 3, 2, 4, 6, 7];
const decreasingSequence = (arr = []) => {
let longest = [];
let curr = [];
// 새로운 감소 구간이 시작될 때,
// 기존 구간이 최장 구간이라면 저장 후 초기화
const setDefault = (newItem) => {
if (curr.length > longest.length) {
longest = curr;
}
curr = [newItem];
};
for (const item of arr) {
// 이전 요소보다 값이 커지면 감소 구간 종료
if (curr.length && item > curr[curr.length - 1]) {
setDefault(item);
} else {
// 같거나 작으면 현재 감소 구간에 추가
curr.push(item);
}
}
// 마지막 구간 처리
setDefault();
return longest.length;
};
console.log(decreasingSequence(arr));코드 동작 원리
이 알고리즘의 핵심 로직은 다음과 같습니다.
1. 두 개의 배열 유지: curr는 현재 진행 중인 감소 구간을, longest는 지금까지 발견한 최장 감소 구간을 저장합니다.
2. 순차 비교: 배열을 순회하면서 현재 요소가 직전 요소보다 크면 감소 흐름이 깨진 것이므로 setDefault를 호출해 새 구간을 시작합니다. 반대로 같거나 작으면 현재 구간에 계속 추가합니다.
3. 마무리 처리: 루프가 끝난 후 마지막으로 남아 있는 구간도 비교해야 하므로 setDefault()를 한 번 더 호출합니다.
이 방식은 배열을 단 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다.
출력 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
4
배열 [5, 2, 5, 4, 3, 2, 4, 6, 7]에서 인덱스 2부터 5까지의 요소인 [5, 4, 3, 2]가 가장 긴 감소 연속 구간이므로, 올바르게 4가 반환되는 것을 확인할 수 있습니다.