[JS] 코딩 테스트 문제 : 연속 부분 수열 2

문제 : 연속부분수열 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가지입니다.

▣ 입력설명

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.

▣ 출력설명

첫째 줄에 경우의 수를 출력한다.

▣ 입력예제 1

5 5
1 3 1 2 3

▣ 출력예제 1

10

내코드

function solution(m, arr) {
  let answer = 0,
    sum = 0,
    answerArr = []; // 연속부분수열 확인용 배열

  // 수열을 의미하는 배열을 순회
  arr.forEach((element, index, array) => {
    // index 번의 숫자를 기준으로 마지막 숫자까지 순회
    for (let i = index; i < array.length; i++) {
      sum += array[i];
      // 기준 숫자와 이후 숫자들과 합을 확인하여 m 을 넘지 않는 경우 즉 정답에 해당하는 연속 부분수열을 저장
      if (sum <= m) {
        answerArr.push(array.slice(index, i + 1));
        answer++;
      } else break; // 숫자를 넘어가면 기준숫자로 만들수 있는 연속 부분수열을 없음을 의미하므로 반복을 멈춘다
    }
    sum = 0;
  });

  console.log(answerArr);
  return answer;
}

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

풀이

1. 수열을 의미하는 배열을 순회하면서 index 번의 숫자를 기준으로 마지막 숫자까지 다시 순회하여 index 번 숫자와 이후 숫자들과 합을 확인하여 m 을 넘지 않는 경우 즉 정답에 해당하는 연속 부분 수열을 저장
2. 숫자를 넘어가면 기준숫자로 만들수 있는 연속 부분수열을 없음을 의미하므로 반복을 멈춘다
3. index 번 숫자와 이후 숫자들과 합을 확인을 위한 반복문은 끝나면 sum 을 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++]; // sum 이 m 합을 넘어가면 lt 을 한칸 옮김
    }
    answer += rt - lt + 1; // 이전에 추가한 중복된 경우의 수를 제외한 부분수열이 되는 경우의 수를 값에 추가
  }
  return answer;
}

※ rt - lt + 1 의미 이해

rt - lt + 1 부분은 이전에 추가한 중복된 경우의 수를 제외한 부분 수열이 되는 경우의 수를 값에 추가하는 부분인데 왜 이런 수식이 나오는지 이해를 위해 자세히 짚어보려 한다.

위 코드는 sum > m 을 넘지 않는 lt, rt 인덱스를 기준으로 이전에 추가한 중복된 경우의 수를 제외한 부분 수열이 되는 경우의 수를 값에 추가하고 있다.

lt=0 rt=0 의 경우 수열 {1} 을 의미하며 부분 수열은 {1} 1개 이다
lt=0 rt=1 의 경우 {1, 2} 을 의미하며 부분 수열은 {1}, {1,3}, {3} 이전 경우의 수 중복을 제외하면 2개이다.
lt=0 rt=2 의 경우 {1, 3, 1} 을 의미하며 부분 수열은 {1}, {1,3}, {3}, {1}, {3,1}, {1,3,1} 경우의 수는 총 6개이다 이전 경우의 수 중복을 제외하면 3 개이다.

lt=0 rt=2 의 경우를 자세히 보면 중복을 제외한 경우의 수는 {1}, {3,1}, {1,3,1} 이다.
중복된 값이 아닌 경우의 수는 생각해보면 간단하게 rt 인덱스의 값 {1} 이 포함한 연속된 부분 수열만 생각하면 된다.
rt 숫자 앞 까지 연속될 수 있는 숫자 조합 즉 여기서는 {1,3}, {3} 이고 이 두 가지 경우의 수에 {1} 붙이는 경우를 생각하면 {3,1}, {1,3,1} 두 가지 경우의 수가 나오고 자기 자신으로 하는 부분 수열 {1} 까지 포함해서 {1}, {3,1}, {1,3,1} 총 3가지가 가능하다.

이걸 수식으로 풀면 rt - lt 는 즉 lt 부터 rt 전까지 중 중복이 되지 않는 rt 와 연속될 수 있는 경우의 수를 의미하게 되고 + 1 은 rt 번째 숫자 단일로 가능한 경우의 수 1개를 합친 것을 의미할 수 있다.
(물론 lt 부터 rt 번째 숫자까지 연속될 수 있는 숫자를 표현하기 위해 rt 의 인덱스 값을 1 증가하기 위함으로 봐도 같은 맥락일 것이다.)

다른 예시를 들면 m = 100 이고 [1,2,3,4,5,6,7,8] 이런 수열에서 lt=0 rt=4 인 상황에서 rt=5 되는 경우 중복을 제외하고 추가되는 경우의 수는 {6}, {5,6}, {4,5,6}, {3,4,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6} 여기서 lt 부터 rt 번째 숫자들의 개수 5는 rt 번째 숫자와 연속될 수 있는 경우의 수와 같다.
거기에 자기 자신이 부분 수열이 되는 경우의 수 +1 해주면 6가지의 경우의 수를 계산할 수 있는데 수식으로 보면 rt - lt + 1 수식이 (5 - 0) + 1 = 6 와 같이 적용됨을 알 수 있다.

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard