javascript - 투 포인터(Two Pointer)

투 포인터(Two Pointer) 알고리즘

투포인터 알고리즘은 이름에서도 알 수 있듯이, 두 개의 포인터를 이용해 배열이나 리스트 등의 자료구조에서 원하는 값을 찾아내는 방법입니다. 주로 정렬된 배열에서 두 수의 합, 연속된 부분 배열의 합 등을 효율적으로 찾을 때 사용됩니다.

아래는 투포인터 알고리즘의 기본 개념을 사용하여, 정렬된 배열에서 두 수의 합이 특정 값인 타겟을 만족하는 첫 번째 쌍을 찾는 자바스크립트 함수입니다.

function twoPointers(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        const sum = arr[left] + arr[right];

        if (sum === target) {
            return [arr[left], arr[right]];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return null;
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 15;

console.log(twoPointers(arr, target)); // [5, 10]

만약 두 수의 합이 타겟 값보다 작다면, left 포인터를 오른쪽으로 한 칸 이동시킵니다. 반대로 합이 타겟 값보다 크다면, right 포인터를 왼쪽으로 한 칸 이동시킵니다. 두 포인터가 만나기 전까지 이 과정을 반복하면서 원하는 값을 찾아냅니다.

console.log의 결과로는 합이 15가 되는 두 수 [5, 10]이 출력됩니다.