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

문제

N개의 수로 이루어진 수열이 주어집니다.이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.만약 N=5, M=5이고 수열이 다음과 같다면

1 3 1 2 3

합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2} , {2, 3}, {1, 3, 1}로 총 10가지 입니다.

 

문제풀이

 투포인터 lt와 rt를 이용하여 조건에 부합한 연속부분수열의 합을 구하고자 한다.

 

연속부분수열의 합이 M의 값과 같거나 클 때까지 포인터 rt를 이동시켜 주며 연속부분수열의 합이 M의 값보다 커질 경우에는해당 연속부분수열의 합이 M의 값보다 작아질 때까지(M이하가 되는 경우이기 때문이다) lt를 이동시켜 주며 해당 요소들을감산해준다.

 

이때 조건 상 연속부분수열의 합이 M과 같거나 작을 경우 해당 포인터가 참조하고 있는 요소는 조건에 부합하는 모든 연속부분수열의

맨 끝 원소에 반드시 포함된다. 

 

예를 들어 위 그림과 같이 rt가 요소 1을 참조하고 있는 해당 요소를 포함한 연속부분수열의 합이 M과 같거나 작을 경우 그 경우가 되는

경우의 수에는 반드시 1이 포함된다. 

만약 그 값이 5일 경우(M의 최댓값)에는 5를 포함한 연속부분수열에 대한 경우의 수는 { 5 }, 총 1가지이다

이때 1을 반드시 포함하는 연속부분수열에 대한 경우의 수는 다음과 같이 구할 수 있다.

 

rt_Num(인덱스) - lt_Num(인덱스)+1

 

코드

function solution(arr) {
  let answer = 0;
  let lt = 0;
  let sum = 0;

  for(let rt = 0; rt < arr.length; rt++) {
    let num = (rt - lt) + 1;
    sum += arr[rt];
    if(sum <= 5) answer += num;
    while(sum > 0) {
      sum -= arr[lt++];
      if(sum <= 5) answer += num;
    }
  }
  return answer;
}

let arr = [1, 3, 1, 2, 3]
console.log(solution(arr));

---

function solution(arr) {
  let answer = 0;
  let lt = 0;
  let sum = 0;

  for(let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    while(sum > 5) 
	/* sum >= 5일 경우로 한다면 포인터 rt로 참조해서 구한 연속부부수열에 대한 경우의 수와 
       동일한 경우의 수를 포인터 lt가 참조하게 되어 중첩되는 문제가 생긴다. */
    {
      sum -= arr[lt++];
    }
    answer += rt - lt + 1;
  }
  return answer;
}

let arr = [1, 3, 1, 2, 3]
console.log(solution(arr));