다음과 같은 숫자 배열이 있다고 가정해 보겠습니다.
const arr = [4, 7, 4, 8, 9, 3];
우리는 이러한 배열을 입력받아, 배열 안에서 인덱스와 값의 크기가 모두 엄격하게(strictly) 증가하는 세 개의 숫자를 찾는 JavaScript 함수를 작성해야 합니다. 이때 세 숫자는 반드시 서로 붙어 있을 필요는 없으며, 연속된 위치에 있어도 되고 서로 떨어져 있어도 됩니다(연속 또는 비연속).
예를 들어 위 배열에서 숫자 7, 8, 9는 각각 인덱스 1, 3, 4에 위치합니다. 값은 7 < 8 < 9로 증가하고, 인덱스 역시 1 < 3 < 4로 증가하므로 두 조건을 모두 충족합니다. 따라서 이 배열에 대해서는 함수가 true를 반환해야 합니다.
접근 방법: 한 번의 순회로 해결하기
가장 효율적인 방법은 배열을 왼쪽부터 한 번만 순회하면서 다음 두 값을 추적하는 그리디(greedy) 기법입니다.
- first: 지금까지 확인한 숫자 중 가장 작은 값
- second: first보다 뒤에 등장하면서 first보다 큰 값 중 가장 작은 값
순회 도중 어떤 숫자가 second보다 크다면, "first < second < 현재 숫자" 관계를 만족하는 세 숫자가 존재한다는 의미이므로 곧바로 true를 반환하면 됩니다.
예제 코드
const arr = [4, 7, 4, 8, 9, 3];
const findMatch = (arr) => {
let first = Infinity;
let second = Infinity;
for (let num of arr) {
if (num <= first) {
first = num; // 지금까지의 최솟값 갱신
} else if (num <= second) {
second = num; // 두 번째로 작은 값 갱신
} else {
return true; // first < second < num 조합 발견
}
}
return false;
};
console.log(findMatch(arr));
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true
코드 동작 과정 살펴보기
입력 배열 [4, 7, 4, 8, 9, 3]에 대해 알고리즘이 진행되는 과정은 다음과 같습니다.
- 4: first가 Infinity이므로 first = 4
- 7: 7 > 4이고 second가 아직 비어 있으므로 second = 7
- 4: 4 ≤ 4이므로 first = 4 (변화 없음)
- 8: 8 > second(7)이므로 즉시 true 반환
결국 인덱스 0, 1, 3에 있는 4 → 7 → 8이라는, 인덱스와 값이 모두 증가하는 세 숫자 조합이 존재함을 확인할 수 있습니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열을 단 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가 변수 두 개만 사용합니다.
참고 사항
배열의 길이가 3보다 작으면 세 숫자를 만들 수 없으므로 항상 false가 반환됩니다. 또한 "엄격하게 증가"라는 조건 때문에 값이 같은 경우(예: 4와 4)는 증가로 간주하지 않는다는 점에 유의하세요.