투포인터

배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘 - 출처: [바킹독의 실전 알고리즘] 0x14강 - 투 포인터

• 인덱스나 위치에 해당하는 포인터를 만들어 특정 조건에 따라 포인터를 움직여 원하는 결과를 얻는 방식

• 주로 원하는 조건을 만족하는 한 쌍(pair)을 찾아내는 데 쓰인다.

대표 문제

정렬된 정수의 배열이 주어질 때, 합이 0이 되도록 하는 첫 번째 쌍을 반환하는 sumZero 함수를 작성하라.

🤔 naive solution

• 배열을 순회하면서 합이 0이 되도록 하는 다른 한 쌍을 찾아낸다.

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

• for문이 중첩되므로 시간 복잡도는 O(N^2)이 된다. 따라서 배열이 아주 크다면 실행 횟수 또한 급격하게 증가하므로 효율적이지 못하다.

😎 good solution

• 투포인터를 사용하면 이중 for문을 사용하지 않고 조건에 따라 포인터를 움직여 원하는 값을 찾아낼 수 있다.

function sumZero(arr) {
  // 값을 가리킬 포인터 2개를 만든다.
  let left = 0;
  let right = arr.length - 1;

  // 두 포인터의 값이 같아지면 더이상 loop를 돌릴 필요가 없다.
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) return [arr[left], arr[right]];
    sum > 0 ? right-- : left++;
  }
}

연습 문제

정렬된 정수의 배열이 주어졌을 때, 고유한 숫자의 개수를 리턴하는 countUniqueValues 함수를 작성하라. (유일한 숫자가 아님에 주의할 것. 예를 들어 [1,2,2,3,3,3]이라는 배열이 주어진다면 countUniqueValues의 값은 3이다.)

🤔 나의 풀이

• 처음에는 배열에 하나만 존재하는 숫자인 줄 알았으나, 다른 풀이를 보고 고유한 숫자의 의미를 알았다. 그래서 다시 작성했다. 두 개의 포인터를 만들어 가리키는 값이 서로 다르면 고유한 숫자가 등장했으므로 count를 증가시켜주고 start 포인터를 이동시켜준다.

function countUniqueValues(arr) {
  let start = 0;
  let end = start + 1;
  let count = 0;

  while (start < arr.length) {
    if (arr[start] !== arr[end]) {
      count++;
      start = end;
    } else {
      end++;
    }
  }
  return count;
}

😎 다른 풀이

• while문을 사용한 나의 풀이를 for문으로 바꾼 차이 정도지만, for문의 변수도 포인터가 될 수 있다 라는 것을 알 수 있었다.

function countUniqueValues(arr) {
  // 포인터 start를 선언한다.
  let start = 0;

  // early return
  if (arr.length === 0) return 0;

  // for문에 선언되는 변수를 또다른 포인터로 활용한다.
  for (let end = 1; end < arr.length; end++) {
    if (arr[start] !== arr[end]) {
      // 고유한 값이 등장할 때마다 1증가시켜준다.
      start++;
      arr[start] = arr[end];
    }
  }
  // 마지막에 1을 더해주는 이유: 맨 처음 나타난 고유한 숫자를 반영하지 않았기 때문에
  return start + 1;
}

• 또한, 이 문제에 한해서 Set을 이용해 중복을 제거하는 간단한 풀이도 가능하다.

function countUniqueValues(arr) {
  const set = new Set(arr);
  return set.size;
}

정리

• 투포인터는 조건에 따라 포인터를 움직여 원하는 값을 찾아내는 알고리즘이다.

• 이중 for문으로 처리되는 작업을 O(N)의 시간 복잡도로 해결할 수 있다.

• 보통 2개의 포인터를 사용하는데, for문에서 선언되는 변수를 포인터로 활용할 수도 있다.