(알고리즘) 연속 부분수열

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

만약 N=5, M=5이고 수열([1, 3, 1, 2, 3])이 주어진다면,
합이 5 이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지이다.

츨력설명

경우의 수를 출력한다.

입력예제

• 5
• [1, 3, 1, 2, 3]

출력예제

10

투 포인트 알고리즘을 이용한다면 비교적 쉽게 해결할 수 있다.
인자로 주어진 숫자 5보다 수열 내 원소들의 합이 적은 조합을 찾는 것이므로
변수로는 sum 과 경우의 수를 세는 answer 그리고 sum이 반복문을 돌면서 인자(5)보다 커질 경우를 대비해서, twoPointer라는 인자를 0으로 세팅해주었다.

반복문을 돌면서, 5보다 적을때까지 answer를 증감시킨다.
반복문을 돌면서 합이 5보다 커진다면, 다시 합에서 arr[twoPointer++]만큼 빼준다.
이렇게 while 문을 돌면서 answer의 숫자는 증가한다.

코드로 이를 적으면 아래와 같다.

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

  for (let i = 0; i < arr.length; i++) {
    while (sum <= m) {
      sum += arr[i];
      answer++;
    }
    if (sum > m) {
      sum -= arr[twoPointer++];
    }
  }  
  return answer;
}

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

console.log(solution(arr, m));