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

---

문제 링크

---

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000

입출력 예 설명

입출력 예 #1

길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

---

• 우선 원형 수열이라는 점에서 슬라이딩 윈도우 기법을 사용해야 겠다는 점을 캐치하였고 중복되는 값을 제외한다는 점에서 set함수를 사용해야겠다는 점을 캐치하였다. 슬라이딩 윈도우 알고리즘 사용엔 익숙치 않아서 간단한 문제라고 생각했지만 서치를 열심히해서 풀었다 하하

---

function solution(elements) {
    const set = new Set();
    //Set 객체를 생성하여 중복을 허용하지 않는 고유한 값의 집합을 저장. 중복을 제거하기 위해 사용
    const length = elements.length;
    
    for ( let i=1; i <= length; i++ ) {     //i는 부분 배열의 길이
        let sum =0;		//슬라이딩 윈도우
        for (let j=0; j<=length; j++) {     //j는 현재 부분 배열의 시작 인덱스
            if ( j === 0 ) {        //j가 0이면 첫 번째 부분을 계산
                sum = elements.slice(0,i)       //현재 부분 배열을 가져온 후 
                    .reduce((acc, cur) => acc+ cur,0);}     //reduce 함수를 사용하여 부분 배열의 합을 계산 후 sum에 할당
            if (j !== 0 ) {     //j가 0이 아니라면 첫 번째 부분 배열 이후의 부분 배열을 계산
                sum -= elements[j-1];       // 이전 합에서 이전 부분 배열의 첫 번째 요소를 빼고, 현재 부분 배열의 마지막 요소를 더하여 sum을 갱신
                sum += elements[(j + i-1) % length];        //length가 초과하는 경우를 고려하여 (j + i-1) % length를 사용. 윈도우가 배열의 끝을 넘어가면 다시 처음부터 윈도우를 이어서 처리.
                }
            set.add(sum);
            }
        }   
    return set.size;        //set의 크기, 즉 서로 다른 부분 합의 개수만을 반환
}

---

• i는 현재 부분 집합의 길이이고 j는 부분 집합 시작 인덱스이다.
• j + i-1 는 윈도우의 끝 인덱스를 계산하고 있다.

---

reduce는 배열 요소를 하나씩 순회하면서 누적 계산을 수행하는 JavaScript 배열 메서드이다. 배열의 각 요소에 대해 지정된 콜백 함수를 실행하고, 이전 값과 현재 값을 조합하여 단일 값으로 축소한다.

const numbers = [1, 2, 3, 4, 5];

const sum = numbers.reduce((accumulator, currentValue) => {
  return accumulator + currentValue;
}, 0);

console.log(sum); // 출력: 15

• 위 예제에서 reduce 메서드는 numbers 배열의 모든 요소를 합산하여 sum 변수에 저장한다. 초기값으로 0을 사용하고, 각 요소는 이전 누적 값과 더해지는 방식으로 계산된다. 결과적으로 sum에는 1부터 5까지의 합인 15가 저장된다.

• 이렇게 reduce 메서드를 사용하면 배열을 순회하며 다양한 종류의 누적 계산을 수행할 수 있다.

---

• acc와 cur이 익숙치 않아서 어려웠다. acc와 cur는 화살표 함수의 매개변수이다.

• acc (누적 값): reduce 함수에서 사용되는 누적 값을 나타낸다. 이 매개변수는 이전 요소까지의 계산 결과를 저장한다. 초기 값은 reduce 함수에 전달되는 두 번째 인수로 설정된다.

• cur (현재 값): 배열의 현재 요소를 나타낸다. reduce 함수는 배열의 각 요소를 순차적으로 처리하면서 이 매개변수에 각 요소의 값을 할당한다.

const arr = [1, 2, 3, 4, 5];

const sum = arr.reduce((acc, cur) => {
  console.log("현재 값:", cur);
  console.log("누적 값:", acc);
  return acc + cur;
}, 0);

console.log("결과:", sum);

위를 예시로 들자면 결과 값은

현재 값: 1
누적 값: 0
현재 값: 2
누적 값: 1
현재 값: 3
누적 값: 3
현재 값: 4
누적 값: 6
현재 값: 5
누적 값: 10
결과: 15

이렇게 출력된다.