[JS] 투 포인터(Two-Pointers) : 연속 부분수열

개요

주어지는 배열에서 특정 값을 찾아내는 알고리즘을 작성할 때, 일반적으로 loop문을 두 번 중첩해서 사용합니다.

물론 주어지는 배열의 크기가 10,000 이하인 경우 최대 O(n^2) 내에서 해결하면 되므로 문제가 없으나.... 그 이상이 주어진다면 그 속도는 기하급수적으로 차이가 납니다.

투 포인터 알고리즘은 포인터 두개를 둬서, 시간복잡도를 O(n) 내로 해결하는 방식입니다.

 

문제

주어지는 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하라.

만약 M=6이고 수 열이 다음과 같다면

1 2 1 3 1 1 1 2 

합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지이다.

 

▣ 입력설명

첫째 줄에 M(1≤M≤100,000,000)이 주어진다.

수열의 원소값은 1,000을 넘지 않는 자연수이다.

 

▣ 출력설명

첫째 줄에 경우의 수를 출력한다.

 

▣ 입력예제 1

6

1 2 1 3 1 1 1 2

 

▣ 출력예제 1

3

 

코드

🤩 : 투 포인터 사용하기

function solution(m, arr) {
  let answer = 0;

  let left = 0;
  let right = 0;
  let sum = 0;

  while (left < arr.length) {
    if (right === arr.length) {
      left++;
      right = left;
      sum = 0;
      continue;
    }

    sum += arr[right++];

    if (sum === m) {
      left++;
      right = left;
      sum = 0;
      answer++;
    }
  }
  return answer;
}

// 테스트
describe('연속 부분수열1', () => {
  it('기본 테스트 케이스', () => {
    let a = [1, 2, 1, 3, 1, 1, 1, 2];
    expect(solution(4, a)).toEqual(4);
  });
});

- left, right 포인터 두 개를 선언하고 while loop문으로 제어합니다.

- 이 경우 시간 복잡도는 O(n)입니다.

 

생각해야할 것

보통 배열이 주어지고 특정 값을 찾아 비교하거나 연산을 하는 문제는 for 중첩문을 사용할 가능성이 큽니다.

입력값이 크지 않다면 위에 언급했듯 고려사항이 아니나, 이런 문제는 충분히 함정이 될 수 있기 때문에 잘 유의해서 풀어야 합니다.

 

코드를 먼저 짜다보니 답은 맞지만 효율성이 틀리는 것을, 로컬 환경에서는 확인하기 쉽지 않으니 다시 한 번 더 생각해야겠습니다.