연속 부분 수열의 합 구하기

프로그래머스 코딩테스트에 나온 문제인데 원으로 이어진 순열로 

기존 배열보다 훨씬 더 많은 부분배열을 만들어 낼 수 있었고,

그 부분배열의 합을 중복없이 갯수를 구하는 문제였다.

 

프로그래머스에서[7,9,1,1,4]로 나타낼 수 있는 결과값은 아래와 같았다.

길이가 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]

 

나는 힌트를 참고해서 풀었다.

function solution(elements) {
const set = new Set();
for(let i=1; i<=elements.length;i++) {
const ele = elements.concat(elements.slice(0,i));
    
for(let j =0; j<elements.length; j++) {
set.add(ele.slice(j,i+j).reduce((a,b) => a+b,0))
}
}
    return set.size
}

이런식으로 문제를 해결했다.

풀이를 살펴보면 set으로 중복값이 들어오면 추가되지 않도록 설정해주었다.

 

그리고 concat을 이용하여 i가 증가할 때마다 기존 배열에서 slice하여 주어진 elements배열을 확장시켜나갔다.

 

for문 안에 for문에서는 확장된 배열을 가지고 slice와 reduce로 배열의 원소 합을 구했고, set.add로 값을 추가해주었다.

여기서 만약 이미 set안에 있는 값이 추가되려하면 set에 의해서 추가되지 않는다.

 

그리고 모든 계산이 끝나면 set.size로 전체 갯수를 return해주었다.

 

 

문제에서 제시된 원형수열이라는 부분이 굉장히 흥미로웠는데

for문에서 concat과 slice를 이용해 원소를 추가하는 법을 기억해야겠다.