프로그래머스 Lv.2 연속부분수열합의개수

💁🏻 코드

function solution(elems) {
    const extendedElems = [ ...elems, ...elems.slice(0, elems.length - 1)];
    const sumSet = new Set();
    for (let i = 0; i < elems.length; i++) {
        let sum = 0;
        for (let j = 0; j < elems.length; j++) {
            sum += extendedElems[i + j];
            sumSet.add(sum);
        }
    }
    return sumSet.size;
}

입력값의 제한은 다음과 같습니다.

• 3 <= elements 배열의 길이 <= 1,000

배열 elements에 대해 이중 for문을 돌려도 무방하겠다고 생각했습니다.
Set 자료형을 사용한 이유는 당연하지만 중복되는 값을 제거하기 위해서 입니다.
문제의 핵심은 extendedElems 배열을 설정하는 것입니다.
[7, 9, 1, 1, 4, 7, 9, 1, 1] 값을 갖는데 마지막에 4를 추가하지 않은 이유는 연속 부분 수열의 합을 구할 때 [7, 9, 1, 1, 4]가 불필요하게 중복되기 때문입니다.
참고로 sum 변수에 대해 누적값을 할당하는 이유는 다음과 같습니다.

• 시작점 인덱스가 0인 경우
  • 인덱스 0에 해당하는 수를 세트에 넣고(길이가 1인 부분 수열의 합을 구하고), 여기에 인덱스 1에 해당하는 수를 더해서 세트에 넣고(길이가 2인 부분 수열의 합을 구하고), ..., 여기에 인덱스 4에 해당 하는 수를 더해서 세트에 넣고 (길이가 5인 부분 수열의 합을 구하고)
• 시작점 인덱스가 1인 경우
  • 인덱스 0에 해당하는 수를 세트에 넣고(길이가 1인 부분 수열의 합을 구하고), 여기에 인덱스 1에 해당하는 수를 더해서 세트에 넣고(길이가 2인 부분 수열의 합을 구하고), ..., 여기에 인덱스 4에 해당 하는 수를 더해서 세트에 넣고 (길이가 5인 부분 수열의 합을 구하고)

...

• 시작점 인덱스가 4인 경우
  • (반복)

각 과정을 거치면 길이가 0인 부분 수열의 합, 길이가 1인 부분 수열의 합, ..., 길이가 5인 부분 수열의 합의 모든 경우의 수를 따져줄 수 있습니다.