[JS] 다중 포인터(투 포인터)

투 포인터

배열이나 리스트에서 투 개의 포인터(인덱스)를 사용하여 문제를 해결하는 방법이다.

이 두 개의 포인터를 각각 배열의 다른 위치에 두고,

그 위치를 조절하면서 원하는 값을 찾아가는 방식이다.

주로 배열의 특정 구간을 탐색하거나, 부분합을 구하는 문제에 사용된다.

 

투 포인터가 필요한 이유

만약 배열에서 두 수의 합을 찾는 문제가 있다고 가정해 보자.

배열의 모든 쌍을 하나하나 비교하면 시간이 많이 걸리는데,

이때 투 포인터를 사용하면 훨씬 더 빠르게 결과를 구할 수 있다.

 

투 포인터의 작동

1. 포인터 두 개 설정

배열의 시작과 끝, 혹은 배열의 두 위치에 각각 포인터를 설정한다.

이 두 포인터는 우리가 탐색하려는 범위를 나타낸다.

 

2. 조건에 맞게 포인터 이동

두 포인터를 움직이면서 배열을 탐색한다.

 

2-1. 예시

두 숫자의 합을 찾고 있다고 가정해 보자.

두 숫자의 합이 목표 값보다 작으면, 더 큰 수를 찾기 위해 왼쪽 포인터를 오른쪽으로 이동시킨다.

두 숫자의 합이 목표 값보다 크면, 더 작은 수를 찾기 위해 오른쪽 포인터를 왼쪽으로 이동시킨다.

 

3. 종료 조건

포인터가 서로 교차하거나, 더 이상 조건에 맞는 값이 없을 때 탐색을 멈춘다.

 

투 포인터의 예시

배열에서 두 숫자의 합이 10이 되는 쌍을 찾아보자.

배열이 [1, 3, 5, 7, 9] 일 때:

1. 포인터 설정:

    - 왼쪽 포인터는 배열의 첫 번째 요소인 1에 위치

    - 오른쪽 포인터는 배열의 마지막 요소인 9에 위치

2. 합 계산:

    - 첫 번째 시도: 1 + 9 = 10 -> 정답! (포인터를 멈추거나 다른 쌍을 찾기 위해 이동시킨다.)

3. 다음 탐색:

    - 만약 더 많은 경우를 찾고 싶다면 왼쪽 또는 오른쪽 포인터를 이동하면서 탐색을 계속한다.

 

투 포인터의 예시 코드

// 주어진 배열
const arr = [1, 3, 5, 7, 9];

// 목표로 하는 합
const target = 10;

// 투 포인터 알고리즘을 위한 두 개의 포인터 설정
let left = 0; // 왼쪽 포인터는 배열의 시작을 가리킴
let right = arr.length - 1; // 오른쪽 포인터는 배열의 끝을 가리킴

// 두 포인터가 만날 때까지 반복
while (left < right) {
  // 왼쪽 포인터와 오른쪽 포인터가 가리키는 두 숫자의 합을 계산
  const sum = arr[left] + arr[right];

  // 두 숫자의 합이 목표 값과 같다면
  if (sum === target) {
    console.log(`합이 ${target}인 쌍을 찾았습니다: (${arr[left]}, ${arr[right]})`);
    left++;  // 왼쪽 포인터를 한 칸 오른쪽으로 이동
    right--; // 오른쪽 포인터를 한 칸 왼쪽으로 이동
  }
  
  // 두 숫자의 합이 목표 값보다 작다면
  else if (sum < target) {
    left++; // 합을 키우기 위해 왼쪽 포인터를 오른쪽으로 이동
  }
  
  // 두 숫자의 합이 목표 값보다 크다면
  else {
    right--; // 합을 줄이기 위해 오른쪽 포인터를 왼쪽으로 이동
  }
}

// 결과
합이 10인 쌍을 찾았습니다: (1, 9)
합이 10인 쌍을 찾았습니다: (3, 7)