[programmers] 연속 부분 수열 합의 개수

📝 [Lv2] 연속 부분 수열 합의 개수

👀 문제 설명

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

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

 

🚨 제한 사항

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

 

💻 입출력 예

elements	result
[7,9,1,1,4]	18

 

✨ 풀이 설명

원순열의 부분 수열 합이 나올 수 있는 경우의 수를 구하는 문제이다.
원순열은 시작 부분이 정해져 있지 않기 때문에 리스트를 두 번 반복하여 어디서 시작하든 부분 수열을 만들 수 있도록 하였다.
reduce를 두 번 반복해 주었는데, 처음 반복문은 시작을 모든 위치에서 하기 위해 돌려주었다. 각 시작 부분부터 전체 개수만큼을 새로운 배열로 만들어 해당 배열에 대해 부분 수열의 합을 구해주었다.

외부의 reduce는 set을 반환하는데, 이 set에는 각 부분 수열의 합을 추가해 주었고, 내부 reduce가 반환하는 sum은 전체 개수만큼 새로 만든 배열에 대해 하나씩 더해가며 부분 수열의 합을 저장해 주었다.
예를 들어 새로운 배열이 [1, 3, 5, 2] 일 경우, 처음에는 1, 그다음에는 3을 더한 4, 그다음은 9, 마지막은 11이 된다. 이 합들을 set에 추가해주기만 하면 된다.

마지막에 이 set의 크기를 반환하면 전체 원순열 부분 수열의 개수를 구할 수 있다.

 

🕵️‍♂️ 코드

function solution(elements) {

  const len = elements.length, elementList = [...elements, ...elements];

  return elements.reduce((set, _, i) => {

    elementList.slice(i, i + len).reduce((sum, ele) => {

      set.add(sum + ele);

      return sum + ele;

    }, 0);

    return set;

  }, new Set()).size;

}