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

문제 설명

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

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

제한사항

3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000

입출력 예

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

입출력 예 설명

입출력 예 #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]

풀이

예시로 설명을 해보자면, 7,9,1,1,4는 길이 5인 연속 부분 수열까지 만들 수 있다.
예시의 마지막 인자인 4의 경우, [4,7,9,1,1]까지 하여 길이 5인 연속 부분 수열을 만들 수 있는 것이다.
따라서, 배열을 중복해서 이어 새로운 배열을 만들어 원형 수열에서 벗어날 수 있다.
또한, 중복해서 이은 새로운 배열에서 가장 마지막 인자는 사용하지 않으므로 제거해줘도 된다.

EX
[7,9,1,1,4] + [7,9,1,1,4] = [7,9,1,1,4,7,9,1,1,4] 새로운 배열 생성
원래 배열은 길이 5인 연속 부분 수열까지 만들 수 있기 때문에 새로운 배열의 마지막 인자는 사용하지 않는 숫자이다.
예시: [7,9,1,1,(4,7,9,1,1),4] //()괄호 부분이 길이 5인 마지막 연속 부분 수열.

concat()과 pop()을 사용해 새로운 배열을 생성해준다.
이후 이중for문을 이용한다.
첫 번째 for문은 0부터 elements의 길이-1까지,
두 번째 for문은 i부터 i+elements의 길이-1까지로 정해준다.

EX
i=0일 때,j=0~4  =>  [7], [7,9], [7,9,1], [7,9,1,1], [7,9,1,1,4]
i=1일 때,j=1~5  =>  [9], [9,1], [9,1,1], [9,1,1,4], [9,1,1,4,7]
i=2일 때,j=2~6
i=3일 때,j=3~7
.
.
.

두 번째 반복문 내부에서는 다음을 반복해준다.
1. sum을 0으로 초기화
2. 임시배열 t에 새로운 배열의 i번째 인덱스부터 j번째 인덱스까지를 부여
3. 임시배열 t의 sum값 구한 후, sum값들을 넣어 줄 배열 Nums에 sum넣어주기

반복문이 다 끝나면 nums의 중복값을 제거해준 뒤, nums의 길이를 출력해준다.

function solution(elements) {
    var answer = 0;
    var nums = [];
    var t = [];
    var sum = 0;
    var temp = elements.concat(elements);
    temp.pop();
    
    for(let i=0; i<elements.length; i++){
        for(let j=i; j<i+elements.length; j++){
            sum = 0;
            t = temp.slice(i,j+1);
            t.forEach(n => {
                sum+=n;
            });
            nums.push(sum);
        }
    }
    
    answer = [...new Set(nums)].length;
    return answer;
}

사실 코드는 한 번에 통과했지만, 시간초과가 날 수도 있을 것 같다는 생각이 든다.
추후에 코드를 수정해보아야겠다.