[프로그래머스 - JS] level.2 연속 부분 수열 합의 개수

 

 

프로그래머스

---

나의 풀이 

 

 

<시간 초과 풀이>

function solution(elements) {
    const inbox = new Set()
    // 길이 i인 연속 부분 수열
    for( i=1; i<=elements.length; i++) {
        // 모든 수 순회
        for(j=1; j<elements.length; j++){
            // 길이에 맞게 더하기
            for(k=0; k+i<=elements.length; k++) {
             inbox.add(elements.slice(k,k+i).reduce((a,b) => a + b))
            }
            elements.push(elements.shift())
       } 
    }
    return inbox.size
}

원래는 이렇게 풀 생각이었다. 

하지만 중첩문이 많아 시간 복잡도에 의해 시간초과다

첫 번째 for문은 길이를 결정해주고

두 번째 for문은 배열을 순회시켜준다 

예를 들어  [ a, b ,c d ] 가 있고 길이 2라고 한다면

a+b / a+c / a+d  / b+c / b+d / c+d 이렇게 계산해줘야하는데 

나의 for문에 의하면 a + b / b+c / c + d /  이렇게 밖에 못해줘서 배열 앞에서 요소하나를 빼고 다시 뒤로 넣어서 

임의로 배열을 돌려서 계산한다. 

그러면 [ a , b, c d] 배열이 있다면 

[ b, c, d ,a ] 

[c, d, a, b ]

[ d, a , b, c] 이렇게 3개의 배열이 더 만들어져서 전부 순회하며 더할 수 있지만 이렇게 풀면 시간초과이고 불필요한 동작이 들어간다. 

따라서

 

<통과한 풀이>

function solution(elements) {
    const inbox = new Set()
    // 길이 i인 연속 부분 수열
    for( i=1; i<=elements.length; i++) {
        const newElements = elements.concat(elements.slice(0, i));
         for(k=0; k<elements.length; k++) {
             inbox.add(newElements.slice(k,k+i).reduce((a,b) => a + b))
            }
    }
    return inbox.size
}

 

이런식으로 원래 배열에 앞부분 부터 점차 잘라서 뒤에 붙여주는 식으로 해서  

마지막에는  [a, b, c, d] 배열이 있다면 [a , b, c , d, a, b, c, d] 이렇게 만들어져서 계산을 한다. 

결국에는 모든 경우 이상을 순회하기는 하지만 통과는 할 수 있다. 

그렇게 마음에드는 풀이는 아니다.

---

다른 사람 풀이 

 

function solution(elements) {
    const circular = elements.concat(elements);
    const set = new Set();
    for (let i = 0; i < elements.length; i++) {
        let sum = 0;
        for (let j = 0; j < elements.length; j++) {
            sum += circular[i + j];
            set.add(sum);
        }
    }
    return set.size;
}

이 풀이가 처음에 생각했던 것인데 별로일 것 같아서 다르게 풀었지만 이게 더 좋은 것 같다. 

  const circular = elements.concat(elements);

이 부분이 핵심인 것 같다.