투포인트 JS

투포인트란 배열에서 포인트를 2개를 가지고 배열을 탐색하는 방법이다.

 

예제)

[1, 2, 2, 5, 7, 7, 99 ]

배열에서 중복이 아닌 숫자의 갯수를 얻어내려면??

이중 for문으로 i 와 j 를 두고 모두 탐색하면 방법도 있겠지만 그건 for 문이 2번이니 On^2 를 가지게 된다.

 

i와 j를 가진다는 점에서는 비슷하지만 투포인트 기법으로 하게되면 O(n) 의 결과를 얻게 된다.

 

예제)

[-4, -3, -2, -1, 0, 1, 2, 5] 이 배열에서 서로 더 한 값이 0이 되는 수를 찾아서 반환한다.

코드를 살펴보자,

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

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

// 2중for On^2

말그대로 하나씩 다 훑는다. 완전탐색 브루트포스라고 볼수있을까? 아직 정확하게 개념을 배운게 아니라서 맞다고 정의는 못하겠지만 느낌상 맞는것같다..

2중 for문을 while 문으로 바꿔버리면 O(n)의 결과를 얻을 수 있다.

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++;
    }
  }
}
console.log(sumZero([-4, -3, -2, -1, 0, 1, 2, 5]));

left 와 right 투포인트로 풀어나갈수 있다.

 

예제2)

 

배열에서 서로 다른 숫자의 갯수를 찾아보자

function countUniqueValues(arr) {
  if (arr.length === 0) return 0;

  let i = 0;

  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }

  return i + 1;
}

console.log(countUniqueValues([1, 2, 2, 5, 7, 7, 99]));

이 문제는 left 0 rigth 1 으로 시작부터 2중for문이 아닌 while 문으로 훑는데 O(n) 이다.

 

left를 0으로 두고 right 가 하나씩 탐색하는데 i와 다른 숫자가 나오면 arr의 i 번째에 rigtht 의 값을 넣어주고 

ex) 1, 2, 2, 5, 7, 7, 99 -> 2, 2, 2, 5, 7, 7, 99 => 1과 2가 달라서 1에 2를 넣어준다.

 

이렇게 탐색을 한 뒤 i의 위치를 보면 갯수를 알 수 있다.

 

투포인트는 이렇게 2개의 포인트를 두고 범위를 점차 좁혀가거나 늘려가면서 원하는 값을 찾는 방법