[알고리즘 | JS] 다중 포인터(Multiple pointers)패턴

🍕다중 포인터 패턴이란?

 ※공식이름은 아닙니다. 편의상 부르는 이름이 '다중 포인터'

 

이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점 or 끝 지점 or 양쪽 지점을 향해 이동시키는 것이다. 

(creating pointers or value that correspond to an index or postion and move towards the beginning, end or middle based on a certain condition )

 

Very efficient for solving problems with minimal space complexity as well

 

결론적으로 말하자면 배열이나 문자열과 같은 일종의 선형 구조(linear Structure)나 이중 연결 리스트나 단일 연결 리스트를 만드는 것이다.  ->한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다면 개념(보통 한 쌍을 찾음)

• 두 가지의 참조값(여기서 참조값이란 index를 가리키는 숫자인 i, j 등의 변수를 의미)을 사용한다.
• 포인터 변수란 배열이나 문자열의 특정 위치를 가리키는 것이다.
• 어느 방향으로 진행하든지 상관은 없지만 중요한 것은 두 개의 포인터를 이용한다는 점이다. 

---

예시를 통해 이해하기 

정렬(sorted)된 배열을 취하는 sumZero 라는 함수를 만들어라. 다만 오름차순(작은 값-> 큰 값으로 정렬)이어야 한다. 
-sumZero함수는 합이 0이되는 첫번째 pair(요소 2개)를 찾아야 합니다. 
-짝이 있는 경우, 반환값은 합이 0인 값들을 담은 배열, 짝이 없는 경우는 undefined를 반환합니다. 

 

예시1: 두 값의 합이 0이 되는 배열을 반환하는 함수 만들기

(Naive solution과 해당 코드를 refactor한 코드)

/* Example
오름차순(값이 작은 것 -> 큰 것)으로 정렬(sorted)된 배열을 취하는 sumZero 라는 함수를 만들어라.  
명심할 점은 인수로 넘겨받는 배열이 꼭 정렬되어 있어야 한다는 것입니다. 그래야 해당 패턴에 적용가능
-sumZero함수는 합이 0이되는 첫번째 pair(요소 2개)를 찾아야 합니다. 
-짝이 있는 경우, 반환값은 합이 0인 값을 담은 배열, 짝이 없는 경우는 undefined를 반환합니다. 

the result should be...
sumZero([-3,-2,-1,0,1,2,3]) // [-3, 3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined
*/

//Naive Soultion (a.k.a- 순진한 솔루션, 작동은 하지만 비효율적인 솔루션을 말함)
// 아래 예시코드의 시간복잡도: O(N^2), 공간복잡도 O(1)
// 이중 for 문으로 중첩 루프이니 시간 복잡도가 n^2임
function sumZero(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] + arr[j] === 0) {
        return [arr[i], arr[j]];
      }
    }
  }
}

//refactored solution! (multi-pointer pattern이 적용됨)
// 배열의 맨 왼쪽과 오른쪽을 포인터로 잡고 두개를 비교하는 것 중앙으로 좁혀지면서 비교
// 즉, 포인터가 치음과 끝에 존재하고 가운데로 방향 이동하면서 비교하는 것
// 시간 복잡도: O(n), 공간복잡도 O(1)
function refactoredSumZero(arr) {
  //변수에 할당된 값은 index를 의미
  let left = 0;
  let right = arr.length - 1;
  //while의 조건식에서 left < right이라고 명시한 이유는 동일한 값에 left와 right가 같이 걸려서
  // '같은 수 -(빼기) 같은 수'를 하면 안되기 때문이다. 
  // 이런 점을 방지하기 위해 미만이라고 정의
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}
const result = refactoredSumZero([-5, -4, -3, -2, 0, 1, 2, 3, 4]);
for (const value of result) {
  console.log(value);
}

예시2: 고유값을 찾는 Counter 만들기

다중 포인터 문제2: countUniqueValue, 고유값을 세는 과제
오름차순으로 정렬된 배열의 고유값을 세시오. 음수가 있어도 됩니다.

*힌트: 포인터를 앞에 두 개 i와 j로 두고 j만 배열의 끝까지 순회한다. i는 고유값을 표현한다.

function countUniqueValue(arr) {
  if (arr.length === 0) {
    return 0;
  }
  let i = 0;
  for (let j = 0; j < array.length; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i + 1;
}
console.log(countUniqueValue([1, 3, 3, 4, 5, 5, 7, 7, 7, 9]));
/*
i j 출력값 아래
1 1
1 2
2 3
3 4
3 5
4 6
4 7
4 8
5 9

결과: 6
*/

코드 설명

• 해당 코드는 두개의 포인터 i와 j를 갖는다. 두 포인터의 방향은 왼쪽부터 시작해서 오른쪽으로 향한다.
• for루프에서 변수 j를 초기화하고 있기 때문에 따로 빼서 정의하지 않아도 된다. for문을 통해서 j를 배열 끝까지 순회하게 만든다. 하지만 i의 경우는 순회하지 않기 때문에 해당 예시의 시간 복잡도는 O(n) 선형 타임이다. 
• i는 맨 왼쪽 요소를 뜻하기 때문에 index를 0인 포인터로 지정을하고 j의 경우, i와 비교해야 하기 때문에 index가 1인 것을 뜻하기 위해 for문에서 let j = 1로 초기화했다. 
• if문에서 i와 j의 값이 같지 않다면 i를 하나 증가시키고 그 자리에 j의 값을 넣어준다. i와 j의 값이 같을 경우는 아무 작업도 하지 않는다. j의 경우는 for문에서 자동으로 증감하고 있기 때문에 i와 별개로 증가시키지 않아도 된다. for문을 다 돌고 리턴값으로 i + 1을 한 이유는 결과적으로 i가 가리키고 있는 값이 index이기 때문에 +1을 해줘야 고유값을 제대로 출력할 수 있다. 
• 맨 위에 if 조건절은 사용자가 빈 배열을 입력했을 때 결과가 for문의 구절을 아무것도 실행하지 않더라도 마지막줄의 return i + 1 을 통해 1이 되기 때문에 이 점을 방지하기 위해 배열의 길이가 0일 때(빈 배열일 때)는 0을 리턴하도록 명시해줍니다.

-> 두 예시의 핵심은 정렬된(sorted) 배열을 썼다는 점입니다. 배열이 오름차순으로 정렬되어 있지 않다면 해당 패턴을 적용하기 까다로워 집니다.