5-3 연속 부분수열 1

문제

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

풀이

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

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

lt 와 rt 두개의 포인터 변수를 설정하였습니다.

 

만약 lt부터 rt 까지의 합을 sum 이라고 하고 만약 sum 이 목표한 m 값보다 작다면 rt를 증가하며 sum에 더해줍니다

 

그리고 sum이 m과 같거나 m보다 커진다면 lt를 빼준후 lt값을 증가시켜줍니다.

 

또한 sum이 m과 같을 때 answer에 카운팅을 해줍니다. ++

 

이러한 작업을 rt가 arr.length 보다 작을때까지만 해줍니다. 

 

 

다른 풀이

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

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

위의 코드를 간략화한 코드입니다