JS 다중 포인터 패턴

다중 포인터 패턴 (투 포인터)

• 선형 자료구조에서 주로 사용된다. (배열, 연결 리스트)
• 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 , 특정 조건에 따라 중간 지점에서부터 시작, 끝, 양쪽 지점을 향해 이동시키는 것이다.
• 기본 반복을 사용하면 (이중 루프) O(N^2) 의 시간복잡도를 나타낸다.
• 올바른 탐색 패턴을 사용하면 O(N)의 시간복잡도를 나타낸다.

예시 문제

주어진 배열에서 두 수의 합이 0 이되는 두 값을 찾아 배열로 반환

테스트 케이스

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

기본 중첩 루프 사용 해답 - O(N^2)

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

투포인터를 활용한 해결 - O(N)

• 공간복잡도 : O(1)

  // 패턴을 사용한 해결 : O(N)
  function sumZero_solution(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++;
    }
  }
  }
  

문제 1

• 정렬된 배열을 받는 함수 countUniqueValues가 있다.
• 전달된 배열에서 고유한 값의 개수를 세어 반환하는 함수를 작성하라
• (배열의 요소에는 음의 정수가 있을 수 있다.)
• (배열은 항상 정렬 되있다.)

테스트 케이스

countUniqueValues([1, 1, 1, 1, 1, 2]); // 2개 : 1과 2 두개의 고유값만 존재
countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13]); // 7개
countUniqueValues([]); // 0
countUniqueValues([-2, -1, -1, 0, 1]); // 4개

나의 해답

function countUniqueValues_mine(arr) {
  if(arr.length === 0) {
    return 0;
  } else if (arr.length === 1) {
    return 1;
  }
  const set = new Set(arr);
  return [...set].length;
}

• Set 자료형을 사용하여 중복을 해결하였다.
• 찾아보니 Set은 공간복잡도가 높았다.

강의 해답

function countUniqueValues_solution(arr) {
  //배열을 변환가능한 점을 이용한것
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    if(arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i+1;
}

배운점

• Set이라는 자료형을 알게 되었다. 더 알아봐야 한다.
• Pointer 라는 개념을 두고 위치를 정하여 순회하는 방식이 상당히 합리적이다.
• 시간복잡도를 계산하는데 아주 조~~~금 익숙해졌다.
• 공간복잡도는 아직 확실하게 계산 못하겠다.

강의

• Udemy : Javascript 자료구조 & 알고리즘 마스터 클래스