투 포인터 알고리즘이란?

코딩테스트 문제를 풀다 보면 배열이 주어지고 

주어진 배열 중에서 원소를 더하여 특정 숫자를 만드는 문제가 출제되곤 한다.

 

완전탐색을 통해 모든 경우의 수를 구해서 답을 얻는 방법도 있지만 시간 부분에서 효율성이 떨어진다.

이 때 사용할 수 있는 방법이 바로 투 포인터이다.

 

완전 탐색과 투 포인터의 차이점은 시작점에 있다.

먼저 완전 탐색을 살펴보자

 

//정렬되지 않은 배열과 두번째 인자로 n이 주어질 때
//배열 안의 두 값의 합이 n이 되는 경우의 수를 반환하시오.
//조건을 충족하지 않으면 false를 반환하시오.

function getNumber(arr, n) {
  arr.sort((a,b) => a - b);
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === n) {
        result++;
      }
    }
  }
  return result > 0 ? result : false
}

흔히 이렇게 문제를 푼다.

배열을 정렬하고 두 개의 숫자이므로 for문 안에 for문을 사용하여 전체 경우를 탐색한 뒤 결과를 반환한다.

이렇게 하면 시간 측면에서 효율적이지 못하다.

 

이제 투 포인터를 살펴보자.

//정렬되지 않은 배열과 두번째 인자로 n이 주어질 때
//배열 안의 두 값의 합이 n이 되는 경우의 수를 반환하시오.
//조건을 충족하지 않으면 false를 반환하시오.

function getNumber(arr, n) {
  arr.sort((a,b) => a - b);
  let p1 = arr.length - 1 //index에 접근해야 하므로 전체 길이에서 1을 빼준다.
  let result = 0;
 
  for(let i = 0 ; i < arr.length ; i ++) {
  if(i === p1) break; // 두 포인터가 같아지면 종료한다.
  const number = arr[i] + arr[p1]
  if(number === n) result++;
  
  if(number > n) {
  p1--;
  i--; //합이 더 크므로 p1은 -1해주고, 다음 계산에서 i도 그대로여야 하므로 -1해준다.
  }
 }
  return result > 0 ? result : false;
}

이런식으로 p1을 조작함으로써 경우의 수를 많이 단축시킬 수 있다.

이렇게 하면 완전탐색보다 더 쉽고 빠르게 원하는 결과를 얻을 수 있다.