[algorithm] Multiple Pointers Pattern (다중 포인터 패턴)

Multiple Pointers Pattern (다중 포인터 패턴)

 

다중 포인터 패턴은 배열에서 여러 개의 포인터를 사용하여 포인터를 이동시키면서 문제를 해결하는 방법입니다. 이 패턴은 배열이나 문자열처럼 순서가 있는 데이터 집합에서 공간 복잡도를 낮추면서 효율적으로 문제를 해결할 수 있게 해줍니다.

 

특징

 

• 포인터 생성 및 이동: 인덱스나 위치에 대응하는 포인터를 생성하고, 조건에 따라 시작, 끝, 또는 중간을 향해 이동시킵니다.

• 효율성: 최소한의 공간 복잡도로 문제를 해결할 수 있어 매우 효율적입니다.

 

예시 문제

 

예시 1: 두 요소의 합이 0이 되는 첫 번째 요소 쌍 찾기

 

문제

정렬된 배열이 주어졌을 때, 두 요소의 합이 0이 되는 첫 번째 요소 쌍을 배열로 반환하는 함수를 작성하세요. 해당하는 쌍이 없으면 undefined를 반환합니다. (배열이 정렬되어 있다는 점이 중요합니다.)

 

예시

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

 

코드

// 시간 복잡도 O(N), 공간복잡도 O(1)
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--; // 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 이동
    } else {
      left++; // 합이 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동
    }
  }
  
  return undefined;
}

 

설명

 

• 배열의 왼쪽 끝에 left 포인터, 오른쪽 끝에 right 포인터를 두고 시작합니다.

• left와 right 포인터 위치의 값을 합산하여 결과가 0이면 두 값을 배열로 반환합니다.

• 합이 0보다 크면 오른쪽 포인터를 왼쪽으로, 0보다 작으면 왼쪽 포인터를 오른쪽으로 이동합니다.

• 이 방식으로 중첩 루프 없이 O(N) 시간 복잡도로 문제를 해결할 수 있습니다.

 

예시 2: 고유한 요소의 개수 세기

 

문제

정렬된 배열이 주어졌을 때, 배열 내 고유한 요소의 개수를 반환하는 함수를 작성하세요.

 

예시

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

 

코드

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

 

설명

 

• i 포인터는 배열의 처음부터 시작하고, j 포인터는 그 다음 요소부터 시작합니다.

• arr[i]와 arr[j]의 값이 다르면, i를 증가시키고 arr[j]의 값을 arr[i] 위치에 복사하여 고유한 값을 기록합니다.

• 두 포인터를 이동시키며 배열을 순회한 후, i + 1을 반환하여 고유한 요소의 개수를 계산합니다.