JavaScript 배열에서 만들 수 있는 등차수열(AP) 개수 계산하기

등차수열(Arithmetic Progression)이란?

등차수열(AP, Arithmetic Progression)은 연속된 두 수의 차이가 항상 일정한 수열을 의미합니다. 이 일정한 차이를 '공차(common difference)'라고 부릅니다.

예를 들어 1, 2, 3, 4, 5, 6… 은 공차가 1인 등차수열입니다(2 − 1 = 1).

문제 설명

정수로 이루어진 배열 arr을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수의 목표는 주어진 배열에서 크기가 3인 등차수열의 개수를 반환하는 것입니다. 각 등차수열을 이루는 원소들 사이의 차이는 서로 같아야 하며, 입력 배열은 항상 오름차순으로 정렬되어 있다고 가정합니다.

입력 예시

const arr = [1, 2, 3, 5, 7, 9];

출력 예시

const output = 5;

출력 설명

배열 안에 다음과 같은 등차수열들이 존재하기 때문입니다 −

[1, 2, 3], [1, 3, 5], [1, 5, 9], [3, 5, 7] and [5, 7, 9]

접근 방법

핵심 아이디어는 간단합니다. 세 수 a, b, c가 등차수열을 이루려면 가운데 값이 양 끝 값의 평균, 즉 b = (a + c) / 2를 만족해야 합니다.

따라서 양 끝의 두 원소(arr[i], arr[k])를 먼저 선택하고, 그 합이 짝수일 때만 평균값을 계산합니다. 그런 다음 두 원소 사이에 위치한 원소들 중 평균값과 일치하는 값이 있는지 확인하여 카운트를 늘립니다. 이 방식은 삼중 반복문을 사용하므로 시간 복잡도는 O(n³)입니다.

구현 코드

다음은 전체 코드입니다 −

const arr = [1, 2, 3, 5, 7, 9];
const countAP = (arr = []) => {
    let i, j, k;
    let { length: len } = arr;
    let count = 0;
    for (i = 0; i < len - 2; i++){
        for (k = i + 2; k < len; k++){
            let temp = arr[i] + arr[k];
            let div = temp / 2;
            if ((div * 2) == temp){
                for (j = i + 1; j < k; j++){
                    if (arr[j] == div){
                        count += 1;
                    }
                }
            }
        }
    }
    return count;
};
console.log(countAP(arr));