[JS] 연속 부분 수열 합의 개수

 

 

난이도: Lv.2

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

프로그래머스

 

 

알고리즘

1. len은 길이가 얼마인 연속 부분 수열인지를 나타낸다. len이 가질 수 있는 값의 범위는 1이상 elements 배열의 길이 이하이다.

2. 부분 수열 합을 위해 몇 번째 원소부터 더 할 것인지 정해야한다. 이 값을 i라 하자.

3. 2.의 i번째 원소부터 몇 개를 더할것인지 정해야한다. 1.에서 길이가 len이라고 정의했으므로 i번째 원소부터 i - len - 1 원소까지 더해야한다. 따라서 0부터 len - 1까지 값을 증가시키는 변수를 j라 하자. 쉽게 말하면 몇 번째 원소부터 몇 개를 더할것인지를 나타내는 변수가 각 for문의 i와 j이다.

4. 이 문제는 원형 수열이다. 맨 마지막 원소에 접근한 후 다음 원소에 접근하려면 맨 처음으로 돌아가야 한다. 따라서 주어진 elements 배열의 길이로 나머지 연산을 한 것을 인덱스로 사용하여 원형 수열로 동작하게 만들어 준다.

5. 덧셈의 결과를 Set에 넣어준다. 이 문제에서는 연속 부분 수열 합으로 만들 수 있는 수의 개수를 알고싶은 것이므로 똑같은 수가 중복되어서는 안되기 때문에 Set을 사용한다.

 

 

코드

function solution(elements) {
    const sumSet = new Set();

    for (let len = 1; len <= elements.length; len++) {
        for (let i = 0; i < elements.length; i++) {
            let temp = 0;
            for (let j = 0; j < len; j++) {
                temp += elements[(i + j) % elements.length];
            }
            sumSet.add(temp);
        }
    }

    return sumSet.size;
}

 

 

주저리

3중 for문 쓰면서 망했군~ 했는데 통과돼서 띠용이였다.

시간 박살난 것 같은디