[Algorithm] (알고리즘 패턴) 투 포인터(다중 포인터)

투 포인터(Two Pointers. 다중 포인터) 알고리즘 패턴

두 개 또는 그 이상의 포인터를 두고 값들을 비교하여 문제를 해결하는 알고리즘 패턴이다.

• 배열이나 문자열같은 선형 구조에서 각자 다른 원소를 가리키는 2개의 포인터를 조작해가면서 원하는 것을 얻어내는 개념이다. 
• 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 한다.

 

프로세스

그냥 기본 방식인 탐색(반복문)을 쓰다 보면 시간이 오래 걸리거나 시간 초과가 걸리는 경우에 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있다.

시간복잡도 : O(N). 기본 탐색 반복문을 사용한다면 O(N^2)

투 포인터는 2가지 방식이 있다.

• 앞에서 시작하는 포인터와 끝에서 시작하는 포인터
• 빠른(Fast runner)가 느린 (Slow runner)보다 앞서는 형식

 

형식 1. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터

정렬된 배열에서 첫번째로 합이 0이 되는 쌍을 찾는 함수 

두 포인터가 하나는 처음, 하나는 끝 인덱스에서 중앙으로 이동하는 예제

여기서 중요한 점은 배열의 중복 수가 없어야 하고, 수열이 정렬되어 있어야 한다.

출력 예시)

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

패턴을 적용하지않고 풀이 해보면

const arr = [-4, -3, -2, -1, 0, 1, 2, 5];

const solution = 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(solution(arr)); // [-2, 2]

이중 루프를 이용해서 시간복잡도 O(N^2), 공간복잡도(1) 으로 해결할 수 있다.

이 방법으로도 해결은 가능하지만, 배열의 항목이 많아지면 많아질수록 반복횟수는 아주 많이 이루어지게 된다.

이때 시간 복잡도를 효율적으로 가져갈 수 있는 것이 투 포인터다.

투 포인터 패턴을 적용

const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
        //left(-4)                  right(5)     ---- 1
const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
        //left(-4)              right(2)         ---- -2
const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
            //left(-3)          right(2)         ---- -1
const arr = [-4, -3, -2, -1, 0, 1, 2, 5];
                //left(-2)      right(2)         ---- 0 [-2, 2] 출력

배열의 값이 오름차순인 것을 알고 있기 때문에 가장 작은값인 -4와 가장 큰값인 5를 포인터 left, right로 둔다

1. -4와 5를 더하면 1 --> 양수 (더해서 0이 되는 쌍을 찾아야하기 때문에 right를 작은쪽으로 한칸 옮긴다.)
2. -4와 2를 더하면 -2 --> 음수 (작은값 포인터 left를 큰쪽으로 한칸 옮긴다.)
3. -3과 2를 더하면 -1 --> 음수 (작은값 포인터 left를 큰쪽으로 한칸 옮긴다.)
4. -2와 2를 더하면 0 --> 쌍을 찾았으므로 출력한다.

코드로 작성해보면

const arr = [-4, -3, -2, -1, 0, 1, 2, 5];

const solution = arr => {
  let left = 0; //제일 처음 인덱스
  let right = arr.length - 1; // 마지막 인덱스

  while (left < right) {//포인터가 같은 곳을 가리키거나 서로 교차되면 값을 못찾았으므로 loop 끝
    let sum = arr[left] + arr[right];

    if (sum === 0) {//합이 0이면
      return [arr[left], arr[right]];
    } else if (sum > 0) {// 양수면
      right--;
    } else {//음수면
      left++;
    }
  }
  //값을 못찾았다면 여기서 default로 undefined가 리턴된다
};

console.log(solution(arr)); // [-2, 2]

시간복잡도 O(N), 공간복잡도(1) 으로 해결할 수 있다.

 

형식 2. 빠른 포인터(Fast runner)가 느린 포인터(Slow runner)보다 앞서는 형식

정렬된 배열에서 요소의 가짓수를 구하는 함수

두 포인터가 첫 인덱스에서 끝으로 이동하는 예제

풀이

1. 두 포인터 slow와 fast는 각각 인덱스0과 1에서 시작한다.
2. fast가 인덱스 1부터 증가하게 되면서 조건(두 포인터의 숫자가 다르면)이 맞으면 slow를 앞으로 이동한 후, 그 숫자를 fast 포인터가 가리키는 숫자로 바꿔준다.

출력 예시) 

console.log(solution([1, 1, 1, 1, 1, 2])); // 2
console.log(solution([1, 2, 3, 4, 4, 4, 7, 7, 12, 12, 13])); // 7
console.log(solution([])); // 0
console.log(solution([1])); // 1
console.log(solution([-2, -1, -1, 0, 1])); // 4

const solution = arr => {
  let slow = 0;
  let fast = 1;
  
  if (arr.length === 0) return 0;

  while (fast < arr.length) {
    if (arr[slow] !== arr[fast]) {
      slow++;
      arr[slow] = arr[fast];
    }
    fast++;
  }
  return slow + 1;
};

solution([1, 1, 1, 1, 1, 2])의 동작순서를 보면

//p1은 i , p2는 j로 설명
const arr = [1, 1, 1, 1, 1, 2];

 i
[1, 1, 1, 1, 1, 2]
 j							// arr[i]와 arr[j]는 같으므로 j++
 
 i
[1, 1, 1, 1, 1, 2]
    j						// arr[i]와 arr[j]는 같으므로 j++
    
 i
[1, 1, 1, 1, 1, 2]
       j					// arr[i]와 arr[j]는 같으므로 j++

 i
[1, 1, 1, 1, 1, 2]
          j					// arr[i]와 arr[j]는 같으므로 j++
          
 i
[1, 1, 1, 1, 1, 2]
             j				// arr[i]와 arr[j]는 같으므로 j++
             
 i
[1, 1, 1, 1, 1, 2]
                j			// arr[i]와 arr[j]는 다르므로 i++ 후 arr[i]에 arr[j]를 대입 j++		

    i
[1, 2, 1, 1, 1, 2]
                   j        //j < arr.length를 만족하지 않으므로 while문 탈출
                			//i의 i + 1(가짓수)을 리턴한다.

이 문제는 자바스크립트 Set과 spread 연산자를 활용하면 간단하게 해결할수도 있다.

const solution = arr => {
  const uniqueArr = [...new Set(arr)];
  return uniqueArr.length;
};