다중 포인터 (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)