[알고리즘] 연속 부분수열 2 (투포인터 알고리즘)

문제

N개의 수로 이루어진 수열이 주어집니다.

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

풀이

const M = 5;
const arr = [1, 3, 1, 2, 3];

function solution1(M, arr) {
  const N = arr.length;
  let lt = 0;
  let count = 0;
  let sum = 0;

  for (let rt = 0; rt < N; rt++) {
    // 현재까지 부분집합의 합계를 구하기 위해 sum에 rt 값을 더한다.
    sum += arr[rt];
    // 만약 sum이 M을 초과한다면, lt만큼 빼주고 lt를 앞으로 이동시킨다.
    while (sum > M) sum -= arr[lt++];
    // 이 과정이 끝나고 sum이 M 이하인 경우, 현재 lt부터 rt 값 까지의 부분집합 갯수를 구해 더해준다.
    count += rt - lt + 1;
  }
  return count;
}

const resultl = solution1(M, arr);
console.log(resultl);

현재 원소 까지의 부분집합의 합을 구하기 위해 lt와 rt라는 두 개의 포인터를 사용하는 투포인터 알고리즘 문제이다. 

• lt와 rt 두 개의 포인터를 0으로 초기화 시킨 후, sum이 M을 초과할 때 까지 계속해서 더한다.
• 어느 순간 sum이 M을 초과하는 순간이 오는데, 이 때는 lt를 움직여서 sum에서 lt 가 가리키는 값을 빼 주면 새로운 부분집합이 된다.
• M 이하인 부분집합의 갯수이기 때문에 arr의 각 원소도 부분집합에 포함이 된다. 현재 rt 가 가리키는 원소값을 더했을 때 sum 이 M 이하라면, rt가 가리키는 원소를 포함해 그 이전의 모든 원소를 포함한 부분집합이 여러개 생기는 것이다.
• 따라서 sum 이 M 이하라면 부분집합이 생길 것이고 이 부분집합의 갯수를 rt - lt + 1 로 구해줄 수 있다. sum이 M을 초과하면 lt도 증가되며 빠질 것이기 때문에 각 단계에서 중복되지 않는 부분집합의 갯수를 구할 수 있다. 

코드를 따라가며 각 단계에서 결과값이 도출되는 과정을 설명하면 아래와 같다. 

/*
[풀이과정]

arr = [1,3,1,2,3] 일 때 코드의 풀이 과정.

1. sum = 0, count = 0, lt = 0, rt = 0
- sum에 arr[0]인 1이 더해진다.
- 1 은 M(5)보다 작으므로, count에는 0 - 0 + 1 => 1이 더해진다.(부분집합은 [1])

2. sum = 1, count = 1, lt = 0, rt = 1
- sum에 arr[1] 인 3이 더해진다. 
- 4는 5보다 작으므로, count에는 1 - 0 + 1 => 2가 더해진다. (부분집합은 [1, 3], [3] => 2개)

3. sum = 4, count = 3, lt = 0, rt = 2
- sum 에 arr[2]인 1이 더해진다.
- 5는 5와 같으므로 count에는 2 - 0 + 1 => 3이 더해진다. (부분집합은 [1, 3, 1], [3, 1], [1] => 3개)

4. sum = 5, count = 6, lt = 0, rt = 3
-sum += arr[3] => 7
- 7은 5보다 크므로, while문으로 진입해 lt를 증가시키며 sum에서 빼준다.
- 최종적으로 lt = 2, sum = 3, rt = 3
- 3 - 2 + 1 은 2 이다. (부분집합은 [1, 2], [2] => 2개)

5. sum = 3, count = 8, lt = 2, rt = 4
- sum += arr[4] = 6
- while문으로 진입하여 lt = 3, sum = 5
- 4 - 3 + 1 = 2 부분집합은 [2,3], [3] => 2개이다.

최종적으로 카운트는 1 + 2 + 3 + 2 + 2 => 10개이다. 


*/