개인적으로 가장 좋아하는 알고리즘 패턴인 투 포인터(다중 포인터)에 대해서 알아보도록 하겠다.

실제로 코딩테스트에 많이 나오기도 하고, 복잡한 문제 안에 활용할 수 있으니 이 패턴은 꼭 숙지했으면 한다.

테스트 문제에서 투 포인터를 사용하지 않더라도 풀 수 있지만 효율성(시간 복잡도)을 위해 투 포인터를 사용하면 큰 도움이 될 것이라 생각한다.

투 포인터(다중 포인터)

투 포인터 또는 다중 포인터.
두 개 또는 그 이상의 포인터를 두고 값들을 비교하여 문제를 해결하는 알고리즘 패턴이다.
간단한 예제와 함께 알고리즘 효율성에 대해서도 알아보자.

예제

특정 숫자들이 들어있는 배열이 주어졌을 때, 배열 안에 가장 첫 번째로 두 숫자의 합이 0이 되는 값 2개를 배열에 담아 리턴하는 함수를 만들어보자.
(배열의 값들은 낮은 수부터 정렬되어 있다.)

// 예시
getSumZero([-2, -1, 1, 2, 3]); // [-2, 2] => 배열에서 두 숫자의 합이 0이 되는 가장 첫 번째 수는 -2이다.
getSumZero([-1, 0, 1, 2]); // [-1, 1]
getSumZero([0, 1, 2, 3]); // false => 두 숫자의 합이 0이 되는 숫자는 없다.

흔히 생각하는 방법과 투 포인터라는 알고리즘 패턴을 통해 풀어 보려 한다.

흔히 생각하는 방법

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

보통은 for문 안에 for문을 넣어 푸는 이중 for문 방식으로 두 값의 합이 0인 경우를 찾아서 리턴하여 풀 수 있을 것이다.
그리고 조건문에 걸리지 않으면 최종적으로 false를 리턴하여 마무리한다.

이 방법은 배열 안에 여러 값들을 비교할 때 아마 흔히 사용하는 방법일 것이다. 그리고 코드도 짧고 가독성도 나쁘지 않은 것 같다.

그러나 역시 이중 for문이 가진 단점이라 한다면 시간 복잡도가 O(n^2)이라는 것...

잠깐 딴 얘기지만, 실제 코딩테스트를 할 때는 방법이 생각이 안난다면 이렇게 이중 for문이든 뭐든 일단 문제를 푸는 게 먼저다. 그리고 나서 시간에 여유가 있다면 시간 복잡도를 생각하는 게 낫다.

이때 시간 복잡도를 효율적으로 가져갈 수 있는 것이 투 포인터이다.

투 포인터의 개념

// 포인터 2개를 각 p1, p2라고 하겠다.

// [-2, -1, 1, 2, 3]
//  p1
//                p2

// => p1과 p2의 합을 구한다. (-2 + 3 = 1)
// => 0인가? -> 해당 값 리턴
// => 0보다 작은가? -> p1을 한 칸 올린다.
// ✅ => 0보다 큰가? -> p2를 한 칸 내린다. (1 > 0)


// [-2, -1, 1, 2, 3]
//  p1
//            p2

// ✅ => 0인가? -> 해당 값 리턴

이런 식으로 2개의 포인터를 만들어서 조건에 의해 움직이면 된다. 이 방법으로 진행한다면 하나의 반복문에서 문제를 해결할 수 있다.
이 개념을 토대로 한 번 풀어보고, 아래 내가 작성한 풀이를 보도록 하자.

O(n)의 시간 복잡도로 풀어보기

function getSumZero(arr) {
  let p1 = 0;
  let p2 = arr.length - 1; // p2는 주어진 배열의 맨 뒤에서 부터 시작.

  while (p1 !== p2) { // p1과 p2가 만나면 모든 값을 확인 했으니 반복문 종료.
    const result = arr[p1] + arr[p2];

    if (result === 0) { // 두 값의 합이 0이면 바로 리턴.
      return [arr[p1], arr[p2]];
    }

    if (result > 0) { // 0 보다 크면 p2를 한 칸 내림.
      p2--;
    } else { // 그게 아니면(0보다 작으면) p1을 한 칸 올림.
      p1++;
    }
  }
  
  return false;
}

위 방법은 p1과 p2가 만나는 시점, 즉 결국에 배열 안에 값들을 한 번씩만 확인하면 되기 때문에 O(n)이라는 시간 복잡도를 가진다.
그래서 처음 풀이보다 효율적인 시간 복잡도를 가진다.

마치며(연습문제 포함)

모든 투 포인터 또는 다중 포인터의 방법이 효율적이거나 시간 복잡도 O(n)을 갖는 것은 아닐 수도 있다. 하지만 이런 알고리즘 패턴을 학습하고 숙지하고 있으면 앞으로 마주하게 될 문제를 조금 더 다양한 방법으로 풀 수 있을 것이라 생각한다.

아래 문제를 하나 드리오니 포인터를 활용하여 풀어보시길 바란다.
(이중 for문으로 쉽게 풀 수 있지만 포인터 연습을 위해 시간 복잡도가 별로라도 포인터로 풀어보시길..!)

끗.

// 첫 번째 인자로 정렬되지 않은 숫자가 담긴 배열 arr와 두 번째 인자로 n이 주어질 때,
// 배열 안의 두 값이 n이 되는 경우의 수를 리턴하는 함수를 작성하시오.
// 조건에 충족하지 않으면 false를 리턴하시오.

function countSum(arr, n) {
	// your answer...
}

countSum([8, 9, 1, 3, 12, 4, 8, 2, 3, 1], 11); // 5
countSum([1, 4, 2, 9, 3, 2], 5); // 3
countSum([1, 2, 3, 4], 10); // false
countSum([], 3); // false