[알고리즘] 문제 해결 패턴 (2) 다중 포인터 패턴

다중 포인터 패턴

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

 

👉🏻 배열이나 문자열과 같은 일종의 선형 구조나 이중 연결 리스트나 단일 연결 리스트를 만든다.

👉🏻 한 쌍의 값이나 조건을 충족시키는 무언가를 찾는다.

[-4, -3, -2, -1, 0, 1, 2, 5]
"alksjdalksjdlkasjdlks"

 

참조값이란 인덱스를 가리키는 숫자인 i와 j같은 변수를 의미한다.

j와 j를 시작하여 특정방향으로 이동할 수 있게 참조값을 사용하기도 한다.

 

포인터 변수는 배열이나 문자열의 특정 위치를 가리킨다.

(포인터 변수는 두번째도 있으므로 서로를 향해 이동하거나 같은 방향으로 이동하든 끝에서부터 시작위치로 이동하든 상관없다.)

문제 예시

정렬된 배열을 취하는 sumZero라는 함수를 작성한다. 분류(sorrted)가 아닌 정렬(assorted)된 배열이어야 한다. 오름차순이어야 한다. 이 함수는 합계가 0인 첫 번째 쌍, 즉, 한 숫자를 가져와 다른 숫자에 더하면 0이 되는 쌍을 찾는다. 

sumZero([-3, -2, -1, 0, 1, 2, 3]) // [-3, 3] <- 이 쌍은 배열로 반환된다.
sumZero([-2, 0, 1, 3]) // undefined

 

두 개의 포인터를 사용해 포인터를 아래나 다른 포인터를 위 방향으로 이동시키는 특정 조건을 테스트할 수 있다. 

이건 O(n²)의 시간 복잡도이다.

해결책 예시

function sumZero(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) { // j+1은 중복된요소를 피하기 위해서
      if (arr[i] + arr[j] === 0) {
        return [arr[i], arr[j]];
      }
    }
  }
}

리팩토링

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

 

두개의 포인터를 사용한 리팩토링

 

하나는 왼쪽에서 0의 위치(index)에서 시작하고 다른 하나는 배열의 마지막 위치, 즉, 배열의 길이보다 1작은 값에서 시작한다.