합하면 0인 쌍, 그리고 다중 포인터 패턴

다중 포인터 패턴

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

결론적으로 말하자면, 한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다(보통은 한 쌍을 찾는다)는 개념이다.

예를 들어 다음 예시를 봐보자. 두 가지의 참조값을 사용하게 된다.

[-4, -3, -2, -1, 0, 1, 2, 5]   // or
"aspdiqwejasdlasjdjqwcjxiwqsj"

이러한 상황에서 배열이나 문자열의 양쪽 끝에서 참조값을 시작하여 가운데로 서로를 향해 이동하도록 해주거나 하는 식으로 이동하는 방식이다. 꼭 양쪽 끝에서 가운데로 가는 방향이 아니어도 되고 특정한 방향이 있으면 된다.

여기서 참조값이란 인덱스를 가리키는 숫자인 i와 j같은 변수를 의미한다. 따라서 i를 왼쪽의 마지막에 j를 오른쪽의 마지막에 위치하여 특정 방향으로 이동하게 하면 된다. 다만 포인터를 두 개 사용하는 것이다.
참조값을 포인터 변수라고도 부른다.

이해를 돕기 위해 예시를 살펴보자.
오름차순으로 "정렬된 배열"을 취하는 sumZero 함수는 합계가 0인 첫 번째 쌍, 즉 한 숫자를 가져와 다른 숫자에 더하면 0이 되는 첫 번째 쌍을 찾는다. 만약 합이 0인 쌍이 없다면 undefined를 리턴하면 된다.

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

이 문제는 어떻게 접근해야할까? 위에서 이미 강조했지만 배열은 오름차순으로 정렬되어 있다. 즉 이 점을 활용해나가야한다. 따라서 배열의 가운데 인덱스 이전 부분은 수가 작을 것이고 가운데의 오른쪽 부분은 수가 상대적으로 클 것이다.
따라서 두 개의 포인터를 이용하여 각 포인터를 위로 향하는 방향으로, 아래로 향하는 방향으로 이동시키는 특정 조건을 테스트 할 수 있다.

우선 이를 생각해보지않고 문제를 풀어보자. 이러한 풀이는 다음 소스 코드와 같다.

function sumZero(arr) {
 for (let i = 0; i < arr.length; i++) {
  // i 가 arr[i]일 때, j는 i + 1 인 인덱스부터 루프를 돌며 arr[i] + arr[j]가 0이 되는지 루프를 또다시 돌면서 확인한다.
  for (let j = i+1; j < arr.length; j++) {
    // 그런데 만약, 합이 0인 쌍이 없다고 가정한다면, 실제로 쌍은 없음에도 불구하고 루프는 끝까지 돌아야만 한다. 그만큼 쓸데없는 반복을 굉장히 많이 하게 되고, 결국 비효율적이다.
   if (arr[i] + arr[j] === 0) {
     return [arr[j], arr[i]];
   }
  }
 }
};

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

위 소스의 시간복잡도는 On^2, 공간복잡도는 O(1)가 사용된 간단한 해결책이다.

우리는 이제 다중 포인터 패턴을 알기 때문에, 위의 코드를 리팩토링 할 수 있다. 오름차순으로 정렬되있음을 알기 때문에, 맨 왼쪽이 값이 가장 작고 맨 우측의 값이 가장 클 것임도 또한 알고 있다.
따라서 맨 왼쪽에 포인터를 하나 두고, 맨 오른쪽에 포인터를 하나 두는 것부터 시작하자.
양쪽의 포인터는 현재 포인터가 위치한 값들의 합이 0인지 확인하고, 만약 맞다면 바로 값을 리턴하고 0이 아니라면 이제는 가운데로 서로를 향해 움직이기 시작할 것이다.

하지만 여기서 동시에 움직이는 것은 아니다, 만약 양쪽 끝의 값끼리의 합이 0이 아니라면 두 수의 합이 양수인지 음수인지를 판별한다. 만약 음수라면 맨 왼쪽의 포인터부터 인덱스를 + 1 더해주면서 자리를 옮겨준다. 그런 후 다시금 맨 오른쪽 포인터의 값과의 합이 0이 맞는지 재확인한다. 만약 0이 아니라면 다시 합이 음수인지 양수인지 판별한다. 만약 양수라면 이제는 오른쪽 포인터를 왼쪽으로 한 칸 움직여준다.

다중 포인터 패턴은 이런 식으로 작동한다.
이제 실제 리팩토링된 코드를 봐보도록 하자.

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--; 
  }
 }
};

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

리팩토링된 소스코드의 시간복잡도는 On이면 공간복잡도는 O(1)이다.