연속부분수열2(Two Pointers Algorithm)

안녕하세요^^

6을 sum에 더하고 처리하는 과정에서 rt-lt+1 가 계산될때 rt=0, lt=1 이므로 rt-lt+1값은 0이 되어 answer에 0을 더하게 되므로 답은 정확하게 나옵니다.

아래와 같이 출력해보면 이해가 갈겁니다.

function solution(m, arr){
  let answer=0, sum=0, lt=0;
  for(let rt=0; rt<arr.length; rt++){
      sum+=arr[rt];
      while(sum>m){
          sum-=arr[lt++];
      }
      answer+=(rt-lt+1);
      console.log(rt, lt, answer);
  }               
  return answer;
}

let a=[6, 3, 1, 2, 3];
console.log(solution(5, a));

안녕하세요, 인프런 AI 인턴입니다.
hyuri님, 연속부분수열 문제에서 ’M = 5’ 라고 했을 때 주어진 배열 ‘a=[6, 3, 1, 2, 3]’ 내에 6과 같이 M보다 큰 값이 포함되어 있는 경우, Two Pointers Algorithm을 사용하는 문제에서는 어떻게 처리되는지가 궁금하신 것 같습니다.

이런 경우 Two Pointers Algorithm은 기본적으로 두 개의 포인터인 lt와 rt를 배열의 시작 부분에 위치시킨 후, ‘rt’ 포인터를 이동시키면서 합이 ’M’을 초과하는 순간까지의 원소를 확인합니다. 만약 ‘rt’ 포인터가 가리키는 원소의 값 자체가 ’M’을 초과한다면, 그 원소를 포함하는 어떠한 연속 부분 수열도 ’M’이하의 합을 가질 수 없기 때문에, ‘rt’ 포인터를 오른쪽으로 한 칸 이동시키고, ‘lt’ 포인터 역시 ‘rt’ 포인터와 같은 위치로 옮깁니다. 이렇게 ‘lt’ 포인터를 조정함으로써, ’M’을 초과하는 큰 값이 들어올 경우 그 값을 제외하고 새로운 부분 수열의 합을 계산하게 됩니다.

예를 들어 a[0] = 6인 경우를 보면 다음과 같이 처리됩니다:
1. 초기 상태: lt = 0, rt = 0, 합(sum) = a[lt] = 6
2. 합이 M을 초과했으므로 rt를 1 증가시키고, lt도 rt와 같은 위치로 옮깁니다.
3. lt = 1, rt = 1, 이때부터 새로운 부분 수열에 대한 합을 다시 구합니다.

이후에 rt 포인터를 배열의 끝에 도달할 때까지 이동시키면서 부분 수열들의 합이 ’M’ 이하가 되는 경우의 수를 계산하면 됩니다. Two Pointers Algorithm은 이처럼 연속된 수열을 효과적으로 처리할 수 있는 방법 중 하나입니다.

더 궁금한 사항이 있다면 추가 질문 주시면 도와드리겠습니다.