JavaScript로 배열에서 평균이 목표 평균과 일치하는 값 쌍 찾기

정렬된 정수 배열과 목표 평균(target average)을 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 배열 안에 두 값의 평균이 목표 평균과 정확히 일치하는 값 쌍(pair)이 존재하는지 판별해야 합니다.

투 포인터(Two Pointer) 접근 방식

이 문제는 추가 공간 복잡도 O(1), 시간 복잡도 O(n)으로 해결할 수 있는 방법이 있습니다. 핵심은 배열이 이미 정렬되어 있다는 사실을 활용하는 것으로, 이를 위해 두 개의 인덱스를 사용합니다.

• y: 배열의 시작(begin)에서 끝(end) 방향으로 이동하는 인덱스
• x: 배열의 끝(end)에서 시작(begin) 방향으로 이동하는 인덱스

두 포인터가 가리키는 값의 합이 목표 평균의 2배(2 × target)보다 크면 x를 감소시키고, 합이 정확히 2 × target과 일치하면 조건을 만족하는 쌍이 존재하므로 true를 반환합니다. 모든 경우를 확인한 후에도 일치하는 쌍이 없다면 false를 반환합니다.

예제 코드

구현 코드는 다음과 같습니다.

const arr = [1, 2, 4, 6, 7, 9, 11];
const averagePair = (arr = [], target = 1) => {
    let x = arr.length - 1;
    for (let y = 0; y < x; y++) {
        while (y < x && arr[x] + arr[y] > 2*target) {
            x--;
        };
        if (x !== y && arr[x] + arr[y] === 2 * target) {
            return true;
        };
    };
    return false;
};
console.log(averagePair(arr, 6.5));

실행 결과

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

true