알고리즘, 문제해결 패턴, Mulitple Pointers

Mulitple Pointers

Multiple Pointers의 기본 개념은 다음과 같습니다:

1. 포인터 설정: 배열이나 문자열의 시작과 끝, 또는 특정 조건에 따라 포인터를 설정합니다.
2. 포인터 이동: 특정 조건을 만족할 때까지 포인터를 이동합니다.
3. 조건 만족 확인: 포인터가 특정 조건을 만족하는지 확인하여 문제를 해결합니다.

시간 복잡도

Multiple Pointers를 사용하는 알고리즘의 시간 복잡도는 일반적으로 O(n)입니다. 이는 배열이나 문자열을 한 번만 순회하면서 문제를 해결하기 때문입니다.

활용 예시

Multiple Pointers 기법은 다음과 같은 다양한 문제에서 유용하게 사용됩니다:

• 두 개의 포인터를 사용하여 배열 내 특정 조건을 만족하는 요소 찾기
• 중복 요소 제거
• 문자열 내 특정 패턴 찾기
• 정렬된 배열에서 특정 합을 가지는 쌍 찾기

이중 for문 사용

// time complexity o(n^2)

function sumZero(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 undefined;
}

console.log(sumZero([-5, -2, -1, 0, 1, 2, 3]));
console.log(sumZero([-3, -2, -1, 0, 1, 2, 3]));
console.log(sumZero([-2, 0, 1, 3]));
console.log(sumZero([1, 2, 3]));

// sumZero([-3,-2,-1,0,1,2,3]) >> [-3,3]
// sumZero([-2,0,1,3]) >> undefined
// sumZero([1,2,3]) >> undefined

While 문 사용, 단일 for문 사용 ✔

// time complexity o(n)

function sumZero(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
  return undefined;
}

console.log(sumZero([-5, -2, -1, 0, 1, 2, 3]));
console.log(sumZero([-3, -2, -1, 0, 1, 2, 3]));
console.log(sumZero([-2, 0, 1, 3]));
console.log(sumZero([1, 2, 3]));

// sumZero([-3,-2,-1,0,1,2,3]) >> [-3,3]
// sumZero([-2,0,1,3]) >> undefined
// sumZero([1,2,3]) >> undefined

두 개의 포인터를 사용하여 배열 내 특정 조건을 만족하는 요소 찾기

// 정렬된 배열을 받아들이고 배열의 고유 값을 세는 countUniqueValues라는 함수를 구현합니다. 배열에 음수가 있을 수 있지만 항상 정렬됩니다.

function countUniqueValues(arr) {
  let left = 0;
  let right = 1;

  if (arr.length === 0) return 0; // 빈 배열인 경우 0 반환

  while (right < arr.length) {
    if (arr[left] !== arr[right]) {
      left++;
      arr[left] = arr[right]; // 중복되지 않는 값을 왼쪽으로 옮김
    }
    right++;
  }

  return left + 1; // left 인덱스는 0부터 시작하므로 1을 더해 유일한 값의 개수를 반환
}

console.log(countUniqueValues([1, 1, 1, 1, 1, 2])); // 2
console.log(countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13])); // 7
console.log(countUniqueValues([])); // 0
console.log(countUniqueValues([-2, -1, -1, 0, 1])); // 4

 // 기본 세팅 >> left = 0, right = 1
 
 i
[1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]
    j