[Algorithm] 연속 부분 수열 합의 개수 ( Programmers - JavaScript )

문제 설명

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

 

 

 

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements 가 순서대로 주어질 때, 원형 수열의 여속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 soltion 함수를 완성해주세요.

 

 

 

---

 

 

 

제한사항

* 3 <= elements 의 길이 <= 1,000

* 1 <= elements 의 원소 <= 1,000

 

 

 

---

 

 

 

입출력 예

 

 

 

 

---

 

 

 

입출력 예 설명

 

 

 

 

---

 

 

 

문제 풀이

[ 연속 부분 수열 합의 개수 ] 문제는 원형큐의 자료구조를 보여주는 문제였다. 

원형큐의 자료구조 특성상 인덱스의 맨끝(맨끝이 n이라고 가정) 값에서부터 n-1번째의 인덱스까지 더할 수 가 있어야한다.

 

좀더 이해하기 편하게 숫자로 표현하자면, const arr = [1, 2, 3] 이라고 가정한다면 3에서 Loop를 돈다면 3 + 1 + 2 가 가능해져야 한다. 이부분을 해결하기 위해서는 간단하게 배열 + 배열로 확장을 해주면 된다.

 

그렇다면 확장된 배열 extendsArr = [1, 2, 3, 1, 2, 3] 이 될 것이고, 3에서 Loop를 돈다면 3 + 1 + 2 가 되는것을 확인할 수 있다.

 

그렇기 때문에 밑에 코드에서는 확장된 개념을 사용해서 헤결되었고, 중복되는 숫자는 없어야 하기 때문에 set에 값을 저장함으로써 중복되는 숫자 없는 갯수를 확인이 가능해진다.

 

function solution(elements) {
  const totalSet = new Set();
  const extendsEl = [...elements, ...elements];
  const index = elements.length;
 
  for (let i = 0; i < index; ++i) {
    let num = 0;
    for (let j = i; j < i + index; ++j) {
      num += extendsEl[j];
 
      totalSet.add(num);
    }
  }
 
  return totalSet.size;
}

 

 

 

 

 

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스