🎯 투포인터

투포인터는 두개 또는 그 이상의 포인터를 두고 값들을 비교하여 문제를 해결하는 알고리즘 패턴을 의미한다. 예를 들어 특정 숫자들이 들어있는 배열이 주어졌을 때, 배열 안에 숫자 합이 0이 되는 값 2개를 새로운 배열에 담아 리턴하는 함수를 만들어보자.

function getSumZero(array) {
  for (let i = 0; i < array.length; i += 1) {
    for (let j = i + 1; j < array.length; j += 1) {
      if (array[i] + array[j] === 0) return [array[i], array[j]];
    }
  }
  return false;
}

위 방법은 가장 흔한 방법이다. 이중 for문을 사용하여 두 값의 합이 0인 경우를 찾아서 리턴하면 해결할 수 있는 문제이다. 배열의 길이가 짧으면 상관이 없겠지만 이중 for문을 사용하기 때문에 시간 복잡도가 O(n^2)이라는 점이 불편하다. 이때 시간 복잡도를 O(n)에 해결할 수 있는 것이 투포인터이다.

  • 위 예시에서는 시작 인덱스(p1)와 마지막 인덱스(p2) 2개를 정한다.
  • p1과 p2의 합을 구한다. 만약 0이면 새로운 배열에 넣는다.
  • 0보다 작으면 p1을 한칸 올리고, 0보다 크면 p2를 한칸 내린다.
  • p1과 p2가 같아질 때까지 반복한다.

🎯 코드 구현 (JS)

👉 문제 확인하기 : 프로그래머스 - 숫자게임

function solution(A, B) {
  A.sort((a, b) => a - b);
  B.sort((a, b) => a - b);

  let count = 0;
  let a1 = 0;
  let b1 = 0;

  while (b1 <= B.length - 1) {
    if (B[b1] > A[a1]) {
      count += 1;
      a1 += 1;
      b1 += 1;
    } else b1 += 1;
  }

  return count;
}