[알고리즘] 투포인터, 슬라이딩 윈도우 (연속된 부분 수열의 합 js)

투 포인터(Two Pointers)

정렬된 배열에서 시작와 끝을 가리키는 두 개의 포인터를 이용하여 부분 배열을 탐색할 때 활용된다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

 

*비내림차순: 점점 증가하는 수열로 인접한 요소끼리의 수가 같을 수 있다.

구현 방법

[1, 1, 1, 2, 3, 4, 5] 에서 구간 합이 5인 경우를 탐색한다.

합이 5보다 작은 경우에는 구간을 오른쪽으로 확장한다.

 

합이 5보다 큰 경우에는 구간을 왼쪽에서 축소한다.

 

이렇게 구간을 확장하고 축소하는것을 반복하면서 합이 5인 구간을 탐색할 수 있다.

 

function solution(sequence, k) {
  const list = [];
  let [left, right] = [0, 0];
  let sum = sequence[0];

  while (right < sequence.length) {
    // sum이 k보다 크면 왼쪽에서 축소
    if (sum > k) {
      sum -= sequence[left++];
      // sum이 k보다 작으면 오른쪽으로 확장
    } else if (sum < k) {
      sum += sequence[++right];
      // sum이 k면 해당 구간을 배열에 추가하고 투포인터를 오른쪽으로 한칸씩 이동
    } else {
      list.push([left, right]);
      sum += sequence[++right];
      sum -= sequence[left++];
    }
  }

  return list.sort((a, b) => a[1] - a[0] - (b[1] - b[0]))[0];
}

solution([1, 1, 1, 2, 3, 4, 5], 5);

 

sum이 k일 때는

오른쪽으로 한 칸 이동하면 구간합이 반드시 5를 넘기 때문에

왼쪽에서 한 칸을 축소해줌으로써 반복 횟수를 줄일 수 있다.

시간복잡도: O(N)

---

슬라이딩 윈도우(Sliding Window)

투 포인터의 구간의 길이에는 제한이 없다면,

슬라이딩 윈도우는 구간의 길이를 정해둔다.

 

배열에서 연속된 세 수의 합이 6인 경우를 탐색한다.

다음과 같이 구간 탐색을 할 수 있다.

구현 방법

구간 합을 메모한다. [0,2] => 3

left와 right을 1칸씩 오른쪽으로 이동시킨다.

메모에서 left를 빼고, right를 더해주는 과정을 반복한다. 

시간복잡도: O(N)

const slidingWindow = (sequence, target, length) => {
  const result = [];
  let [left, right] = [0, length - 1];

  let memo = sequence.slice(0, length).reduce((a, b) => a + b, 0);
  while (right < sequence.length) {
    if (memo === target) {
      result.push([left, right]);
    }
    memo = (-1 * sequence[left++]) + memo + (sequence[++right]);
  }

  console.log(result);
};

slidingWindow([1, 1, 1, 2, 3, 4, 5], 6, 3);