증가 수열이란?
수열에서 각 요소가 바로 앞의 요소보다 크거나 같은 수열을 증가 수열(increasing sequence)이라고 합니다.
예를 들면 다음과 같습니다.
4, 6, 8, 9, 11, 14 → 증가 수열입니다.
3, 3, 3, 3, 3, 3 → 모든 요소가 같아도 증가 수열에 포함됩니다.
문제 정의
숫자 배열 arr를 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열 안에 연속된 세 요소가 증가하는 구간이 존재하는지 확인해야 합니다.
예를 들어 함수의 입력이 다음과 같다면,
const arr = [4, 1, 5, 7, 3, 1, 4];
출력은 다음과 같아야 합니다.
const output = true;
출력 설명
배열에서 1, 5, 7이 차례대로 연속되어 나타나며, 이 세 값은 1 < 5 < 7 조건을 만족하기 때문입니다.
예제 코드
const arr = [4, 1, 5, 7, 3, 1, 4];
const increasingTriplet = function(arr) {
let first = Infinity;
let second = Infinity;
for (let curr of arr) {
if (curr > second && curr > first) {
return true;
};
if (curr > first) {
second = curr;
}else{
first = curr;
};
};
return false;
};
console.log(increasingTriplet(arr));코드 동작 원리
이 알고리즘은 그리디(Greedy) 방식을 활용해 단 한 번의 순회(O(n))만으로 문제를 해결합니다.
first: 지금까지 탐색한 값 중 가장 작은 값을 저장합니다.second:first보다 뒤에 등장했으면서first보다 큰 값 중 가장 작은 값을 저장합니다.
루프의 각 반복에서 현재 값 curr이 second보다 크고 first보다도 크다면, first < second < curr 관계가 성립하는 것이므로 즉시 true를 반환합니다. 만약 끝까지 그런 조합을 찾지 못하면 false를 반환합니다.
즉, 0 ≤ i < j < k ≤ n-1을 만족하는 i, j, k가 존재하여 arr[i] < arr[j] < arr[k]가 되는 경우가 있으면 true, 그렇지 않으면 false를 반환하는 것입니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true