철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [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 answer = [];
for(let i=1; i<=elements.length; i++){
const array = elements.concat(elements.slice(0,i-1))
// console.log("Array",array)
for(let j=0; j<elements.length; j++){
answer.push(array.slice(j,i+j).reduce((acc,cur)=>acc+=cur,0))
}
}
return [...new Set(answer)].length;
}
원형 수열을 만들어서 ele
의 길이만큼 반복해주면된다.
반복하면서 길이가 1부터 ele.length
까지 각 길이만큼 원형 수열을 잘라주고 그 배열의 합을 구해서
answer
에 넣어줬다.
이렇게 배열을 사용할 경우 중복되는 값이 있기 때문에 new Set
으로 중복을 없애주었다.
근데 생각해보니 Set
으로 중복을 없앨꺼면 처음부터 사용하면 된다..
function solution(elements) {
const set = new Set();
for(let i=1; i<=elements.length; i++){
const array = elements.concat(elements.slice(0,i-1))
// console.log("Array",array)
for(let j=0; j<elements.length; j++){
set.add(array.slice(j,i+j).reduce((acc,cur)=>acc+=cur,0))
}
}
return set.size;
}
set
을 사용하니 코드가 더 깔끔해진것같다.
궁금해서 속도를 비교해봤는데 거의 비슷한듯 하다.
왼쪽이 set 오른쪽이 array 를 사용했을 때 속도