프로그래머스 [Lv. 2] 연속 부분 수열 합의 개수 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(elements) {
    const n = elements.length;
    const setDict = {};
    
    for (let i = 0; i < n; i++) {
        let keyE = elements[i];
        setDict[keyE] = 1;
        for (let j = i+1; j < i+n; j++) {
            const k = j % n;
            keyE += elements[k];
            setDict[keyE] = 1;
        };
    };
    
    var answer = Object.keys(setDict).length;
    return answer;
}

풀이 방법

1. dictionary의 key는 중복되지 않는 점을 이용해서 0번 째 인덱스 부터 시작해서 누적합을 구한다.
2. 누적합을 dictionary에 저장한다.
3. dictionary의 key 개수가 곧 중복되지 않는 합이 된다.

느낀점

• 예전이라면 무조건 set를 썼겠지만 지금 생각해보면 set가 무조건 효율적이지는 않다.
• set는 중복된 수를 찾는 과정이 배열의 길이가 길어질 수록 시간 복잡도가 높아지게 된다.