[JS 알고리즘&자료구조] 다중 포인터 패턴

다중 포인터 패턴은 특정 위치에 해당하는 포인터 변수를 (보통 인덱스) 만든 다음 특정 조건에 따라 한 지점에서 다른 지점으로 이동시키는 방법이다. 이를 통해 배열이나 문자열과 같은 선형 구조 혹은 이중 연결 리스트나 단일 연결 리스트를 결과값으로 반환한다. 보통 한 쌍의 값이나 조건에 해당되는 특정 값을 찾을 때 사용한다.

앞에서 말했듯이 포인터 변수는 배열이나 문자열의 특정 위치를 가리킨다. 인덱스다. 두 개의 포인터가 서로를 향해 이동하던지 혹은 같은 지점에서 같은 방향으로 이동하며 조건에 충족하는지를 검증하는 것이 핵심이다.

아래는 오름차순으로 정렬된 배열을 반환하는 sumZero라는 함수를 만드는 문제이다. 반환 배열에 있는 숫자를 합하면 0이 되는 쌍이 되어야 한다.

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

단순하게(순진하게) 해결할 수 있는 방법은 그냥 이중 반복문을 사용하는 것이다. 각 인덱스에 해당하는 숫자를 나머지 숫자들과 다 대조하여 합이 0이 되는 숫자가 있는지 보는 것이다. 이런 로직을 짜게 되면 배열의 크기가 커질 수록 중첩 루프때문에 반복이 너무 많이 이루어지게 된다. 이런 로직의 리팩토링을 위해 다중 포인터 패턴을 사용한다. 아래 예시를 통해 다중 포인터 패턴이 어떻게 적용되는지 보자.

sumZero([-4,-3,-2,-1,0,1,2,5])

다중 포인터 패턴을 위해 우선 첫번째 숫자와 마지막 숫자에 각각 포인터 변수를 준다. (시작 지점에 있는 포인터를 A, 끝 지점에 있는 포인트를 B라고 하겠다.) 첫번째 숫자와 마지막 숫자를 합산했을 때 양수가 나오니 이 경우엔 B를 한 칸 당겨준다. 그렇게 되면 -4와 2를 합하게 되고 둘의 합은 음수가 나온다. 이럴 땐 A를 한 칸 밀어준다. 현재는 A는 -3, B는 2를 가리킨다. 둘의 합은 음수가 되고 음수가 나오면 다시 A를 밀어준다. A는 -2를 가리키게 되고 다시 2인 B와 합하게 되면 0이 나온다. 이렇게 첫번째 쌍을 찾게 되고 [-2, 2]를 반환해주면 된다. 해당 로직을 코드로 짜보자.

function sumZero(arr) {
  let left = 0;
  lef 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++;
    }
  }
}

위의 방식은 양 쪽에 포인터를 두고 서로를 향하게 만들어서 문제를 해결하였다. 다음 강의에서는 위에서 언급한 바와 같이 둘이 똑같은 지점에 포인터를 두고 한 방향으로 향하는 문제를 풀어보도록 하자.