JavaScript 배열에서 값 차이와 인덱스 거리 조건을 만족하는 두 요소 찾기

문제 개요

정수 배열과 두 개의 양의 정수를 인자로 받아, 특정 조건을 만족하는 두 요소의 존재 여부를 판별하는 JavaScript 함수를 작성해 보겠습니다. 함수는 다음 세 가지 인자를 전달받습니다.

• arr → 정수로 이루어진 배열
• m → 양의 정수 (허용되는 최대 인덱스 거리)
• n → 양의 정수 (허용되는 최대 값 차이)

함수의 목표는 다음 두 조건을 동시에 만족하는 두 요소 a1과 a2가 배열 안에 존재하는지 확인하는 것입니다.

• 두 값의 절대 차이(|a1 − a2|)가 n 이하일 것
• 두 요소 인덱스의 절대 차이가 m 이하일 것

예제 코드

다음은 투 포인터(two pointer) 기법으로 이 문제를 해결한 코드입니다.

const arr = [1, 2, 3, 1, 7, 8];
const findSpecialElements = (arr = [], m, n) => {
    const map = arr
    .map((el, ind) => ({ el, ind }))
    .sort((a, b) => a.el - b.el);
    let left = 0;
    let right = 1;
    while (right < map.length) {
        const diff = Math.abs(map[right].el - map[left].el);
        const range = Math.abs(map[right].ind - map[left].ind);
        if (diff <= n && range <= m){
            return true
        }else if (diff > n){
            left++;
        }else if (range > m){
            right++;
        };
        if (left === right){
            right++;
        };
    };
    return false;
};
console.log(findSpecialElements(arr, 3, 0));

코드 설명

이 알고리즘은 다음 단계로 동작합니다.

1. 배열의 각 요소를 실제 값(el)과 원래 인덱스(ind)를 함께 담은 객체로 변환한 뒤, 값을 기준으로 오름차순 정렬합니다.
2. left와 right 두 포인터를 이용해 정렬된 배열을 순회하면서 값 차이(diff)와 인덱스 차이(range)를 계산합니다.
3. diff ≤ n이고 range ≤ m이면 조건을 만족하는 쌍이 존재하므로 즉시 true를 반환합니다.
4. 값 차이가 너무 크면(diff > n) left를 이동시켜 차이를 줄이고, 인덱스 거리가 너무 크면(range > m) right를 이동시켜 탐색 범위를 조절합니다.
5. 모든 경우를 확인한 후에도 적합한 쌍을 찾지 못하면 false를 반환합니다.

실행 결과

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

true

예제 배열 [1, 2, 3, 1, 7, 8]에서 값 1은 인덱스 0과 3에 두 번 등장합니다. 두 값의 차이는 0(n = 0 이하)이고 인덱스 차이는 3(m = 3 이하)이므로, 두 조건을 모두 충족하여 함수는 true를 반환합니다.

이처럼 배열을 값 기준으로 정렬한 뒤 투 포인터를 활용하면, 단순 이중 반복문(O(n²))보다 효율적으로 조건에 맞는 요소 쌍을 탐색할 수 있습니다.