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

연속 부분 수열 합의 개수

❓ 문제설명

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

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

🚫 제한조건

3 ≤ elements의 길이 ≤ 1,000

1 ≤ elements의 원소 ≤ 1,000

✔ 입출력 예

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

💡 풀이

function solution(elements) {
  const double = [...elements, ...elements]

  const set = new Set()
  for(let i=0; i < elements.length; i++) {
    let sum = 0
    for(let j=0; j < elements.length - 1; j++) {
      sum += double[i+j]
      set.add(sum)
    }
  }

  return set.size + 1
}

📝 해설

 원형 수열의 특징은 마지막 원소 다음이 다시 처음 원소로 이어진다는 것이다. 이 점을 활용해서 해당 부분수열을 2번 이어 붙인 배열을 만들고 첫번째 원소부터 부분수열의 합을 확인하여 set으로 모았다. 이 때 전체를 더하는 건 빼는데 이는 전체를 더한건 모두 똑같은데 모든 원소를 돌면서 무의미하게 반복적으로 더하지 않고 마지막에 set.size + 1 로 하는 것이 더 간단하기 때문이다.

📚 참고자료

- https://kimby.tistory.com/57 (Set 객체)