1️⃣ 문제 설명
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
2️⃣ 제한 사항
- 3 ≤ elements의 길이 ≤ 1,000
- 1 ≤ elements의 원소 ≤ 1,000
3️⃣ 입출력 예
입출력 예 #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]
4️⃣ 나의 풀이
const solution = (elements) => {
const sumSet = new Set();
const len = elements.length;
for (let i=1; i<=len; i++) {
/* 슬라이딩 윈도우 */
let sum = 0;
for (let j=0; j<len; j++) { // 연속 부분 수열 시작 지점의 인덱스
if (j === 0) { // 최초 한 번의 창문에 대해서만 직접 합을 구하기
for (let k=0; k<i; k++) {
sum += elements[k];
}
}
else { // 이후 창문들에 대해서는 이전에 구한 합을 활용하기
sum -= elements[j-1];
sum += elements[(j+i-1) % len];
}
sumSet.add(sum);
}
}
// 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return
return sumSet.size;
}
- 슬라이딩 윈도우 알고리즘 활용
길이(윈도우의 크기)가 1~n인 연속 부분 수열을 연속 부분 수열의 시작 지점만 바꿔가며 살펴볼 것- Set 객체 활용
연속 부분 수열 합으로 만들 수 있는 개수를 return
2개 이상의 연속 부분 수열이 동일한 합을 만들어낼 수 있기 때문에 합 값들을 Set 객체에 저장
유일한 합 값들의 개수를 Set 객체의 size 속성을 통해 구하기
슬라이딩 윈도우 알고리즘
구간의 넓이가 고정되어 있을 경우 구간 합을 구하는 효율적인 방법
