[프로그래머스 Level 2] 연속 부분 수열 합의 개수 - JavaScript

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

✏️ 풀이

function solution(elements) {
    const set = new Set();
    for (let i = 1; i <= elements.length; i++) {
        for (let j = 0; j < elements.length; j++) {
            let seq = elements.slice(j, j + i);
            if (i + j > elements.length) {
                seq = [...seq, ...elements.slice(0, i + j - elements.length)];
            }
            const sum = seq.reduce((acc, v) => acc + v, 0);
            set.add(sum);
        }
    }
    return set.size;
}

부분 수열은 길이가 1부터 elements의 전체 길이 만큼까지 나올 수 있다. 따라서 for문으로 1부터 elements.length까지 순회를 하고, 그 안에서 다시 elements의 첫 번째 요소부터 그 길이 만큼의 부분 수열을 모두 탐색하여 모든 가능한 합의 개수를 구해야 한다. 

 

원형 수열이기 때문에 부분 수열을 구할 때 마지막 인덱스에서 초과한 길이만큼의 요소를 다시 0번째 요소부터 채우게 된다. 따라서 j번째 요소부터 i만큼의 길이를 가지는 부분 수열의 합을 구할 때, i + j가 elements의 길이를 초과하면 초과한 부분을 0번째 요소부터 초과한 길이까지의 요소의 합을 별도로 구해서 더하면 된다.

 

합을 구할 때마다 set에 add하여 중복되지 않은 합들의 집합 set을 구하면 그 size가 정답이 된다.