[프로그래머스 LV2] 연속 부분 수열 합의 개수 JS

문제링크

 

 

---

문제 요점

원형수열 안 연속부분의 합으로 만들수 있는 수가 몇가지?

 

첫번째 풀이(성공)

1. 원형수열이므로 사이클이 생긴다. elements길이 ≤ 1,000이니까 elements를 덧붙여서 cycle배열을 만들 수 있다.
2. 첫번째 갯수별로 순회한다 (선택한 숫자가 1개일 때, 2개일때......n개 일때)
3. 두번째 시작인덱스로 순회한다 (시작인덱스가 0, 시작인덱스가 1.... 시작 인덱스가 n)
4. 이 둘을 합치면 "선택한 숫자가 1개일때 시작인덱스가 0", "선택한 숫자가 1개일때 시작인덱스가 1"... 이런식으로 선택이 되는데 선택된 수의 합sum을 set에 추가한다.
5. set의 size반환

function solution(elements) {
    const set = new Set();
    const cycle = elements.concat(elements)

    for (let count = 1; count <= elements.length; count++) {
        for (let startIndex = 0; startIndex < elements.length; startIndex++) {
            // 시작인덱스에서 갯수만큼의 합을 구한다
            const selected = [...cycle].splice(startIndex, count)
            const sum = selected.reduce((acc, curr) => acc + curr, 0);
            set.add(sum);
        }
    }
    return set.size;
}

 

 

 

 

 

---

두번째 풀이(성공)

문제를 간단하게 생각해보면 각 시작 인덱스부터 n개의 합을 구해 set에 add하는 것이다

 

O^2 가능
슬라이딩 윈도우

가 떠올랐다

 

elements를 2번 덧붙이고 시작인덱스를 0에서부터 element의 크기 즉 window길이 까지 순회한다

window 크기까지의 합을 set에 더한다.

 

function solution(elements) {
    var set = new Set();
    let windowLen = elements.length;
    elements = elements.concat(elements);
    
    for (let startIndex = 0; startIndex < windowLen; startIndex++) {
        let sum = 0;
        for (let count = startIndex; count < startIndex + windowLen; count++) {
            sum += elements[count];
            set.add(sum)
        }
    }
    return set.size;
}

 

확실히 시간이 단축되었다.