Two Pointers

1차원 배열에서 두 개의 포인터를 조작하여 동작하는 Algorithm

투 포인터(Two Pointers) 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.

Problem 1, 특정한 합을 가지는 부분 연속 수열 찾기

$N$ 개의 자연수로 구성된 수열에서 합이 $M$ 인 부분 연속 수열의 개수를 구하시오.

단, 수행 시간 제한은 $O(N)$ 이다.

Explanation

해당 문제는 투 포인터를 활용하여 다음과 같이 해결할 수 있디.

[Step 1]. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
[Step 2]. 현재 부분 합이 $M$ 과 같다면, $count$를 추가한다.
[Step 3]. 현재 부분 합이 $M$ 보다 작다면, $end$를 1 증가시킨다.
[Step 4]. 현재 부분 합이 $M$ 보다 크거나 같다면, $start$ 를 1 증가시킨다.
[Step 5]. 모든 경우를 확인할 때까지 위 과정을 반복한다.

위 과정을 코드로 구현하면 다음과 같다.

const N = 5; // 데이터의 개수 N
const M = 5; // 찾고자 하는 부분합 M
const arr = [1, 2, 3, 2, 5]; // 전체 수열

let count = 0;
let interval_sum = 0;
let end = 0;

for (let i = 0; i < N; i++) { // start를 차례대로 증가시키며 반복  
  while (interval_sum < M && end < N) { // end를 가능한 만큼 이동
    interval_sum += arr[end]; 
    end++;
  }
  
  // 부분합이 M일 때 카운트 증가
  if (interval_sum === M) count++;

  interval_sum -= arr[i];
}

console.log(count);

참고 자료

(이코테 2021) 이것 취업을 위한 코딩 테스트다 - 동빈나