알고리즘 - 투 포인터 (js 예제 구현)

1. 투 포인터(Two pointer)  알고리즘 이란 ? 

배열이나 문자열 같이 선형으로 이루어진 구조에서

각자 다른 값을 가리키는 2 개 혹은 그 이상의 포인터를 두고
값 들을 비교하여 문제를 해결하는 알고리즘 입니다.

---

2. 예제 문제로 이해하기

input = [-2, -1, 1, 0, 1, 2]  answer = [-2, 2]

위와 같이 숫자로 이루어진 배열이 주어졌을 때,
배열의 요소 중 2개의 합이 0 이 되는 경우 중 , 
가장 빠른 경우에서의 두 수를 구하여라! 
(배열은 오름차순으로 정렬되어 있다.)

 

위 예제문제를 풀어보며 이해해 봅시다.

---

2-1. 이중 for문 사용하기  / O(n^2)

function solution() {
  for (let i = 0; i < input.length; i++) {
    for (let j = i + 1; j < input.length; j++) {
      if (input[i] + input[j] === 0) {
        console.log([input[i], input[j]])
        return
      }
    }
  }
}

solution() // [-2, 2]

위와 같이 이중 for문을 사용하는 간단한 풀이를 생각해 볼 수 있습니다.

하지만 위와 같은 코드의 시간 복잡도는 O(n^2) 입니다.

문제의 input 배열의 길이가 길어지면 코드의 효율이 떨어지게 됩니다.

---

2-2. 투 포인터 알고리즘 사용하기  / O(n)

function solution() {
  let leftPointer = 0 // 왼쪽 끝
  let rightPointer = input.length - 1 // 오른쪽 끝

  while (leftPointer < rightPointer) {  
    let sum = input[leftPointer] + input[rightPointer]
    if (sum === 0) {
      console.log([input[leftPointer], input[rightPointer]])
      return
    }
    if (sum > 0) {
       rightPointer --
    }else{
       leftPointer++
    }    
  }
}

solution() // [-2, 2]

투 포인터 알고리즘을 활용한 풀이입니다.

1. 배열의 서로 다른 원소를 탐색할 포인터 left, rightPointer를 만들었습니다.
   
2. 반복문을 돌면서 로직을 수행합니다.
   
   2-1. 두 수의 합이 0이면 두 수를 리턴합니다.
   2-2. 두 수의 합이 0보다 크면 rightPointer를 1 감소 시킵니다.
          (정렬된 배열이므로 오른쪽 포인터를 1 낮추면 합이 낮아집니다.)
   
   2-3. 두 수의 합이 0보다 작으면 leftPointer를 1 증가 시킵니다.
          (정렬된 배열이므로 왼쪽 포인터를 1 증가시키면 합이 높아집니다.)

 

위와 같은 풀이는

배열의 모든 요소를 한 번씩만 확인하면 되기 때문에 O(n)의 시간복잡도를 가집니다.

때문에 input 배열의 길이가 증가하여도 효율적인 탐색이 가능합니다!

 

 

 

3. 결론

모든 상황에서 투 포인터 알고리즘이 효율적인 것은 아니지만,

숙지하면 활용하기 상당히 좋은 알고리즘이다 !

 

 

 

 

 

재밌다 알고리즘!