[알고리즘] 다중 포인터 (Multiple Pointers)

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · 다중 포인터 · Refactored · Multiple Pointers

1. 다중 포인터 (Multiple Pointers)

해당하는 Index에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서 부터 시작, 끝, 양쪽 지점을 향해 이동

문제 설명

  • 정렬된 정수의 배열을 인자로 받아 그 배열 안에서 두 원소의 합이 0가 되는 첫 번째 수열을 반환하는 함수.(선형 구조 , 이중 연결 리스트 , 단일 연결 리스트)

입출력 예

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

2. My Solution

1) 기본 접근법

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

시간 복잡도 O(n2) : 중첩 루프로 인한 시간복잡도 효율성 저하

3. Refactored Solution

1) 두개의 포인터로 While 반복문 실행

function sumZero(arr) {
  //왼쪽 인덱스 포인터 지정
  let left = 0;
  //오른쪽 인덱스 포인터 지정
  let right = arr.length - 1;
  //while문 설정 조건은 왼쪽이 오른쪽보다 크다.
  //만약 조건문이 참이라면, while문 안의 문장들이 실행된다. 거짓이라면, 문장은 그냥 while 반복문 후로 넘어간다.
  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]
sumZero([-4, -3, -2, -1, 0, 5, 10]); // undefined

시간 복잡도 O(N) : 두개의 포인터를 사용한다

공간 복잡도 O(1)