D+4 연속 부분 수열 합의 개수

프로그래머스 코테 풀기

생각했던 포인트

1. 길이 1부터 ~ elements 개수까지 +1씩 포함되도록 늘어나야한다.
   => 배열을 인덱스 0부터 elements개수-1만큼 사용이 필요함
   => elements 배열을 붙인 다음 마지막 값은 필요없으므로 pop 시켰음
   => 근데 어차피 elements개수만큼 반목문 돌리므로 마지막 인덱스 계산에 포함 안된다.
   pop안시키는게 시간복잡도 입장에선 연산 한번 덜하므로 빼는게 더 빠르다.

2. 배열을 합해줄 인덱스들만큼 잘라서 합쳐주기
   => count 변수를 추가할 필요가 없이 바깥쪽 반복문 i값을 활용하면 됐다. count 변수 삭제

3. 마지막 중복되는 값 제거해주기
   Set함수 활용하여 length return해주도록 했다.
   const set = new Set(Arr); -> 배열을 Set객체로 만들어주고
   [...set]으로 다시 배열로 만들어준 다음 length를 사용했다.

4. 다른 풀이를 보니, 배열을 그냥 이어붙이는게 연산속도가 더 빠를 것 같아서 concat으로 수정해주었다.
   GPT에게 물어보니?! 시간복잡도 O(n)으로 동일하고, concat은 새로운 배열을 만들다보니, forEach사용하는 것이 메모리측면에서 더 좋다고 한다.

최종본

function solution(elements) {
    // n개 수의 합 구할 수 있도록 배열 앞에 것들 넣어주기
    // 길이가 1~elements개수의 합까지 배열에 값 넣어주기 
    // 최종적으로 중복되는 값은 제거하고 return해주기 
    const len = elements.length
    elements.forEach((v,i) => elements.push(v))
    let sumArr =[]
    let array =[]
    // 배열 i~i+n까지 잘라서 계산해주기
    for(i=1; i<=len; i++){
        for(j=0; j<len; j++){
        array = elements.slice(j,j+i);
        sumArr.push(array.reduce((acc,cur)=>  {return acc+cur},0))
        }
    }
    const set = new Set(sumArr)
    return [...set].length
}

수정전

function solution(elements) {
    // n개 수의 합 구할 수 있도록 배열 앞에 것들 넣어주기
    // 길이가 1~elements개수의 합까지 배열에 값 넣어주기 
    // 최종적으로 중복되는 값은 제거하고 return해주기 
    const len = elements.length
    elements.forEach((v,i) => elements.push(v))
    elements.pop()
    const arr = elements
    let sumArr =[]
    let array =[]
    // 배열 i~i+n까지 잘라서 계산해주기 
    for(i=1; i<=len; i++){
        for(j=0; j<len; j++){
        array = arr.slice(j,j+i);
        sumArr.push(array.reduce((acc,cur)=>  {return acc+cur},0))
        }
    }
    const set = new Set(sumArr)
    return [...set].length
}

GPT 답변

JavaScript에서 concat과 forEach의 시간 복잡도는 다음과 같습니다:

1. concat
시간 복잡도: O(n)
설명: concat 메서드는 두 배열을 합치는 데 사용됩니다. 여기서 n은 결합되는 배열의 요소 수입니다. concat은 새로운 배열을 생성하고, 각 요소를 복사해야 하므로, 결합하려는 배열의 총 길이에 비례하여 시간이 소요됩니다.
2. forEach
시간 복잡도: O(n)
설명: forEach 메서드는 배열의 각 요소에 대해 주어진 함수를 실행합니다. 여기서 n은 배열의 길이입니다. 이 메서드는 배열의 모든 요소에 대해 한 번씩 함수를 호출하므로, 배열의 길이에 비례하여 시간이 소요됩니다.
핵심 비교
두 메서드 모두 시간 복잡도가 O(n)으로 동일합니다.
concat은 새로운 배열을 만들고 요소를 복사하는 데 추가적인 메모리와 시간이 필요합니다.
forEach는 기존 배열의 요소를 순회하여 작업을 수행하지만, 새로운 배열을 만들지 않으므로 메모리 사용 측면에서 더 효율적일 수 있습니다.
결론적으로, 두 메서드는 시간 복잡도는 같지만, 사용 목적과 메모리 측면에서 차이가 있습니다.