투 포인터 알고리즘

정의

---

• 투 포인터(Two Pointer) 알고리즘이란, 배열이나 컬렉션에서 두 개의 포인터를 이용하여 범위를 조절해가며 특정한 조건을 만족하는 부분을 찾는 기법이다.
• 특히 정렬된 배열이나 컬렉션과 관련된 문제에서 효과적으로 사용된다.
• 핵심 아이디어는 배열의 서로 다른 두 부분을 동시에 반복하는 것이다.
• 일반적으로 시간 복잡도는 O(n), 공간 복잡도는 O(1)이 된다.
  런타임을 최적화하고 공간을 절약하고 싶을 때 사용한다.

고려해야 할 점

---

1. 포인터의 초기 위치 설정
   • 포인터를 어디서 시작하고 어떤 인덱스를 비교할 것인가?
2. 포인터의 이동 방향과 조건
   • 같은 방향으로 이동할 것인가, 다른 방향으로 이동할 것인가?
   • 포인터를 언제 움직일 것인가?
3. 포인터의 중지 조건
   • 포인터를 언제 멈출 것인가?
   • 일반적으로 배열의 반복이 끝날 때나 두 포인터가 교차할 때 중지된다.

동작 방식

---

1. 같은 방향 포인터

• 두 포인터 중 하나는 느린 속도로, 다른 하나는 빠른 속도로 이동한다.
• e.g. 정렬된 배열에서 중복 요소 제거, 연결 리스트 사이클

https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e

2. 역방향 포인터

• 두 포인터 중 하나는 맨 처음부터, 다른 하나는 맨 끝부터 이동한다.
• e.g. 팰린드롬(회문)

https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e

소스 코드 (JS)

---

1. 정렬된 배열에서 중복되는 요소 제거하기

• 같은 방향으로 이동하는 포인터를 이용한다.
• 정렬된 배열이 주어지는 경우에만 작동한다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  let j = 0;

  for (let i = 1; i < nums.length; i++) {
    if (nums[j] !== nums[i]) {
      j += 1;
      nums[j] = nums[i];
    }
  }
  return j + 1;
};

2. 연결 리스트 사이클

• 같은 방향으로 이동하는 포인터를 이용한다.
• 둘 중 하나의 포인터는 느리고, 다른 하나의 포인터는 빠르다.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }
  return false;
};

3. 팰린드롬

• 역방향으로 이동하는 포인터를 이용한다.
• 둘 중 하나의 포인터는 문자열의 맨 처음부터 시작하고, 다른 하나의 포인터는 문자열의 맨 끝부터 시작한다.

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  // 공백제거, 소문자 영문으로 변환, 영숫자만 가능
  const formatted = s
    .split("")
    .filter((ch) => isAlphabetOrNumeric(ch))
    .join("")
    .toLowerCase();

  let left = 0;
  let right = formatted.length - 1;

  while (left <= right) {
    if (formatted[left] !== formatted[right]) {
      return false;
    }
    left++;
    right--;
  }
  return true;
};

function isAlphabetOrNumeric(ch) {
  const code = ch.charCodeAt(0);
  return (
    (code >= 48 && code <= 57) ||
    (code >= 65 && code <= 90) ||
    (code >= 97 && code <= 122)
  );
}

참고

---

• Geeks for Geeks
  • Two Pointers Technique
• 블로그
  • Basics of Two Pointers Technique
  • Two Pointers & Sliding Window
• 관련 알고리즘 문제
  • 리트코드 26번 Remove Duplicates from Sorted Array
  • 리트코드 125번 Valid Palindrome
  • 리트코드 141번 Linked List Cycle