[인프런 | JS] 연속 부분수열 1

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

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의

 

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가지입니다.
▣ 입력설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.
▣ 출력설명
첫째 줄에 경우의 수를 출력한다.
▣ 입력예제 1
8 6
1 2 1 3 1 1 1 2
▣ 출력예제 1
3

 

 

 

1. left와 right 인덱스를 만든다
2. left부터 right까지의 합이 m보다 크면 left++
3. left부터 right까지의 합이 m보다 작으면 right++
4. m과 같으면 cnt++

 

function solution(arr, M) {
    let count = 0;
    let left = 0,
        right = 0;
    let sum = 0;

    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];

        //sum과 M이 동일한 경우
        if (sum === M) {
            count++;
        }
        //sum이 큰 경우 left 증가 시켜서 전체 sum 감소
        while (sum >= M) {
            sum -= arr[left];
            if (sum === M) {
                count++;
            }
        }
    }
    return count;
}

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

// sum이 M보다 작은 경우 : 증가
// -> right 증가
// sum이 M보다 큰 경우 : 감소
// -> left 증가

 

while 문 이용

function solution(arr, M) {
    let count = 0;
    let left = 0,
        right = 0;
    let sum = arr[0];

    while (left < arr.length && right < arr.length) {
        //sum과 M 같은 경우 카운트 증가
        if (sum === M) {
            count++;
        }

        //sum이 M보다 작은 경우 : right를 증가시켜서 sum 증가
        if (sum <= M) {
            right++;
            sum += arr[right];
        } else if (sum > m) {
            sum -= arr[left];
            left++;
        }
    }

    return count;
}

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