JavaScript 배열을 정렬하지 않고 n개 이상의 연속된 숫자가 있는지 확인하는 방법

문제 소개

숫자 배열을 첫 번째 인수로, 그리고 하나의 숫자 n을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수의 목표는 배열을 정렬하지 않은 상태에서 배열 안에 n개(두 번째 인수로 전달된 값) 이상의 연속된 숫자 시퀀스가 존재하는지 확인하는 것입니다.

예를 들어 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [0, 4, 6, 5, 9, 8, 9, 12];
const n = 3;

배열에는 4, 5, 6이라는 세 개의 연속된 숫자가 존재하므로, 함수는 true를 반환해야 합니다.

구현 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [0, 4, 6, 5, 9, 8, 9, 12];
const n = 3;
const findSequence = (arr, num) => {
    if(num > arr.length){
        return false;
    };
    let count = 1;
    for(let i = 0; i < arr.length; i++){
        let el = arr[i];
        while(arr.includes(++el)){
            count++;
            if(count === num){
                return true;
            };
        };
        count = 1;
    };
    return false;
};
console.log(findSequence(arr, n));
console.log(findSequence(arr, 4));

코드 설명

이 알고리즘의 동작 방식은 다음과 같습니다.

1. 초기 검증: 요청한 연속 개수(num)가 배열 길이보다 크면 애초에 연속 시퀀스가 존재할 수 없으므로 즉시 false를 반환합니다.

2. 각 요소를 기준점으로 탐색: 배열의 모든 요소를 순회하면서, 현재 요소(el)보다 1 큰 숫자가 배열에 존재하는지 Array.prototype.includes() 메서드로 반복 확인합니다.

3. 연속 개수 카운트: 다음 숫자가 계속 존재하는 동안 count를 증가시키고, count가 목표값(num)에 도달하면 바로 true를 반환합니다.

4. 카운트 초기화: 더 이상 연속되지 않으면 count를 1로 되돌리고 다음 요소부터 다시 탐색합니다.

참고로 includes()는 선형 탐색(O(n))을 수행하므로, 이 알고리즘의 전체 시간 복잡도는 O(n²)입니다. 배열이 매우 클 경우 Set을 활용한 O(n) 접근 방식을 고려할 수 있습니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true
false

n이 3일 때는 4, 5, 6의 연속 시퀀스가 존재하므로 true가 출력되고, n이 4일 때는 네 개의 연속된 숫자가 없으므로 false가 출력됩니다.