[프로그래머스] 연속 부분 수열 합의 개수 (JavaScript) | 교공 알고리즘 스터디 48주차

연속 부분 수열 합의 개수 | 문제 바로가기

✔ 아래의 캡쳐본은 문제의 일부입니다.
보다 자세한 제한 사항 및 입출력 예시는 위의 링크를 참고해주세요!

⭐ 풀이의 핵심

• 슬라이딩 윈도우 알고리즘 활용
  • 길이(윈도우의 크기)가 1~n인 연속 부분 수열을 연속 부분 수열의 시작 지점만 바꿔가며 살펴볼 것
• Set 객체 활용
  • 연속 부분 수열 합으로 만들 수 있는 개수를 return
  • 2개 이상의 연속 부분 수열이 동일한 합을 만들어낼 수 있기 때문에 합 값들을 Set 객체에 저장
  • 유일한 합 값들의 개수를 Set 객체의 size 속성을 통해 구하기

📝 슬라이딩 윈도우 알고리즘

👉 구간의 넓이가 고정되어 있을 경우 구간 합을 구하는 효율적인 방법!

📝 JavaScript의 Set 객체

[참고] Set - JavaScript | MDN

• Set 객체의 특징
  • 삽입한 순서대로 요소를 순회할 수 있음
  • 유일한 값을 저장 (하나의 Set 내 값은 한 번만 나타날 수 있음)

  const aSet = new Set();
  aSet.add(0); // Set(1) {0}
  aSet.add(1); // Set(2) {0, 1}
  aSet.add(1); // Set(2) {0, 1} 1이라는 값은 이미 set에 존재하기 때문에 또 삽입되지 않는다

• 생성자
  • Set()
• 속성
  • .size: set 객체에 있는 원소의 개수 return
• 메서드
  • .add(value): set 객체에 value 추가
  • .clear(): set 객체에 있는 모든 원소 제거
  • .delete(value): set 객체에 있는 value를 제거하고 성공적으로 제거되었는지 여부를 boolean 값으로 return
  • .has(value): set 객체에 value 원소가 있는지 여부를 boolean 값으로 return
• Set 반복

const mySet = new Set();

// set 내 항목에 대해 반복하며 순서대로 항목을 콘솔에 기록
for (let item of mySet) console.log(item);
// 또는
mySet.forEach(function(value) { console.log(value); });

• 그 외

// Set 객체를 Array 객체로 변환
let myArr = Array.from(mySet);

// Array를 Set으로 변환
let mySet = new Set([1, 2, 3, 4]);

// 교집합
let intersection = new Set([...set1].filter(x => set2.has(x)));

// 차집합
let difference = new Set([...set1].filter(x => !set2.has(x)));

🔽 코드 (JavaScript)

const solution = (elements) => {
    const sumSet = new Set();
    
    const len = elements.length;
    for (let i=1; i<=len; i++) { // 연속 부분 수열의 길이
        /* 슬라이딩 윈도우 */
        let sum = 0;
        for (let j=0; j<len; j++) { // 연속 부분 수열 시작 지점의 인덱스
            if (j === 0) { // 최초 한 번의 창문에 대해서만 직접 합을 구하기
                for (let k=0; k<i; k++) {
                    sum += elements[k];
                }
            }
            else { // 이후 창문들에 대해서는 이전에 구한 합을 활용하기
                sum -= elements[j-1];
                sum += elements[(j+i-1) % len];
            }
            sumSet.add(sum);
        }
        /*****************/
    }
    
    // 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return
    return sumSet.size;
}

✅ 효율성 차이 비교

슬라이딩 윈도우를 활용했을 때 실행 속도가 확연하게 줄어든 것을 확인할 수 있다!

🔽 cf. slice 메서드 및 for문 덧셈 활용 코드

const solution = (elements) => {
    const sumSet = new Set();
    
    const getSum = (arr) => {
        let sum = 0;
        for (let i=0; i<arr.length; i++) sum += arr[i];
        return sum;
    }

    const len = elements.length;
    for (let i = 1; i <= len; i++) {
        for (let j = 0; j < len; j++) {
            if (j + i > len) {
                sumSet.add(getSum(elements.slice(j, len)) + getSum(elements.slice(0, j+i-len)));
            }
            else {
                sumSet.add(getSum(elements.slice(j, j+i)))
            }
        }
    }

    return sumSet.size;
}