연속 부분 수열 합의 개수

공부하며 느낀 점
참조한 페이지

연속 부분 수열 합의 개수

나의 풀이

function solution(elements) {
    let answer = new Set(elements)
    const length = elements.length
    let sum0= 0
    
    for (let i = 0 ; i < length ; i++) {
        sum0+= elements[i]
    }
        
    for (let i = 0 ; i < length ; i++) {
        let sum1 = 0
        let sum2 = 0
        for (let j = 0 ; i+j < length ; j++) {
            sum1 = elements[i] + elements[j]
            sum2 += elements[i+j]
            answer.add(sum1)
            answer.add(sum2)
        }
        answer.add(sum0-sum1)
        
    }

    
    return answer.size
}

원래는 위와 같이 했는데 뭔가 잘 되지 않았다.

function sol0(elements) {
    const answer = new Set();
    const length = elements.length;
    let sum = 0;

    for (let i = 0; i < length; i++) {
        sum = 0;
        for (let j = i; j < length + i; j++) {
            sum += elements[j % length];
            answer.add(sum);
        }
    }

    return answer.size;
}

• const answer = new Set(); : set은 중복값을 허용하지 않는다.

• 두번 째 for문의 j < length + i : i에서 길이만큼 더 가야하니까 이런 조건을 주었다.
• sum += elements[j % length]; : j의 길이가 길이보다 커지면 길이로 나눠서 그 나머지로 요소를 찾고 누적시킨다.
• answer.add(sum); : 그때그때의 누적값을 set에 넣는다.

다른 사람의 풀이

function sol1(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); : 배열 두개를 합쳐서 하나로 만드는 방법이다.
같은걸 두개 만들었으니 유사 원형 수열이 되었다.

속도 비교

시간 복잡도와 조건

시간 복잡도 : $O(N^2)$이다.
조건

• 최악의 경우를 가정하기 위에서 배열을 꽉채웠다.
• 배열의 내용물이 10배 커진 배열을 만들었다.
• 길이가 10배인 배열을 만들었다.

반복 횟수 증가

별다른 특징은 없다.

입력 크기 증가

역시 크기로는 별다른 의미가 없다.

입력 길이 증가

아마도 set의 특성상 새로운 값을 넣을때마다 배열 전체를 참조해서 시간복잡도에서 기대한 것보다 더 큰 값이 증가한 것같다.

또는 set작업 자체는 매우 빠르지만 메모리의 크기에 한계에 달했을지도 모른다.

입력값의 길이를 짧게 만들고 다시해보자

elements의 기본 길이를 1000에서 10으로 줄인 결과이다.

위와 같지만 배열이 1부터 시작하는게 아니라 1000부터 시작하게 만들었다.

실행시간의 절대값은 조금 늘었고, 배율은 줄었다.

공부하며 느낀 점

1. 조건을 너무 세분화해서 나누지말고 단순화할 수 있도록 전제를 어느정도 변형할 필요가 있다.
   예) elements[j % length] 보다는 const circular = elements.concat(elements);

참조한 페이지

Array.prototype.concat()