알고리즘, Two Pointers 기법

Two Pointers 기법이란?

• 배열과 문자열을 다루는 문제에서 자주 사용되는 기법이다.

배열이 한 개일 때 사용 예시

abcdefg 라는 문자열이 있을 때 하나의 포인터는 문자열의 맨 앞인 a 를 가리키고 다른 하나의 포인터는 문자열의 맨 뒤인 g 를 가리킨다. 두 포인터를 움직이며, 로직을 수행하고 정답을 찾아낸다.

배열이 두 개일 때 사용 예시

abcdefg hijklmnop 라는 문자열 2개가 있을 때 하나의 포인터는 첫번째 배열의 맨 앞인 a 를 가리키고 다른 하나의 포인터는 두번째 배열의 맨 앞인 h 를 가리킨다. 두 포인터를 움직이며, 로직을 수행하고 정답을 찾아낸다.

이 방법의 장점

시간 복잡도가 O(n) 을 넘어가지 않는다.

Two Pointer 기법으로 해결할 수 있는 문제 예시

팰린드롬 문제

• 팰린드롬은 뒤에서부터 읽으나 앞에서부터 읽으나 같은 단어를 말한다.
• 이를테면 "eye", "madam", "level", "Hannah" 등..
• Two Pointers 를 이용하면, 첫째 글자와 마지막 글자를 동시에 가리킬 수 있다.
• 첫째 글자와 마지막 글자부터 순차적으로 계속 같아야 한다는 원리를 이용해 쉽게 풀 수 있다.

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;

  while (left < right) {
    if (str[left] != str[right]) {
      return false;
    }

    left += 1;
    right -= 1;
  }

  return true;
}

정렬된 배열에서 합계 찾기 (Two Sum)

• 정렬된 배열에서 각 숫자들이 유니크하다는 가정 하에 특정 타겟 합계를 찾을 수 있다.

[1, 2, 4, 6, 8, 9, 14, 15] 배열이 있을 때, 합해서 13 이 나오는 경우가 있다면 true, 아니면 false 라는 문제가 있다고 가정해보자.

가장 단순한 방법으로 풀면 brute force 를 생각해볼 수 있다.

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

  return false;
}

정렬되지 않고, 값이 유니크하지 않다면, 이 방법도 효율은 나쁘지만, 나름 타당하다.

function smartTwoSum(arr, target) {
  let l = 0;
  let r = arr.length - 1;

  while (l < r) {
    const sum = arr[l] + arr[r];
    if (sum === target) {
      return true;
    }

    if (sum > target) {
      r -= 1;
    } else {
      l += 1;
    }
  }

  return false;
}

정렬이 되어있다는 특성 때문에 오른쪽 포인터를 한칸 줄이면, 총 합계가 줄어들게 되고 왼쪽 포인터를 한칸 줄이면 총 합계가 늘어나게 된다. 각 값들은 유니크하므로 왼쪽 포인터와 오른쪽 포인터가 서로를 교차하는 순간에는 모든 값에 대한 검증이 끝난 상태가 된다.

두 개의 정렬된 배열을 정렬된 하나의 배열로 만들기

배열 [1, 3, 4] 와 배열 [2, 5, 7] 을 [1, 2, 3, 4, 5, 7] 과 같은 정렬된 하나의 배열로 만들어보자.

function getOneSortedArray(sA1, sA2) {
  let p1 = 0;
  let p2 = 0;

  const result = [];

  while (p1 < sA1.length && p2 < sA2.length) {
    const n1 = sA1[p1];
    const n2 = sA2[p2];

    if (n1 < n2) {
      result.push(n1);
      p1 += 1;
    } else {
      result.push(n2);
      p2 += 1;
    }
  }

  while (p1 < sA1.length) {
    const n1 = sA1[p1];
    result.push(n1);
    p1 += 1;
  }

  while (p2 < sA2.length) {
    const n2 = sA2[p2];
    result.push(n2);
    p2 += 1;
  }

  return result;
}

• 처음에는 2개의 포인터를 이용해 값을 비교하며 작은 순서대로 넣는다.
• 값을 비교하고 남은 나머지 숫자는 마저 털어넣으면 끝난다.

Subsequence 인지 검사하기

• Subsequence 란 순서까지 일치하는 부분집합을 말한다.
  • "ace" 는 "abcde" 의 Subsequence 이다.
  • "aec" 는 "abcde" 의 Subsequence 가 아니다.
  • "ade" 는 "abcde" 의 Subsequence 이다.
  • "aed" 는 "abcde" 의 Subsequence 가 아니다.

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  let sp = 0;
  let tp = 0;

  while (tp < t.length && sp < s.length) {
    if (s[sp] === t[tp]) sp += 1;
    tp += 1;
  }

  return sp === s.length;
};