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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

일반 수열의 경우 부분 수열을 앞에서부터 잘라주기만 하면 되는데, 원형수열은 끝에 도달하면 다시 처음으로 돌아가야한다.

그래서 생각한 방법은 다음과 같다. 시간을 꽤나 먹긴 하지만 성공 ,, !
1. elements 배열을 자기 자신과 이어붙여 원형 구조 생성
2. 길이 1부터 N까지의 모든 연속 부분 수열 탐색
3. 각 부분 수열의 합 Set에 넣어 중복 제거

코드

---

1. Python

def solution(elements):
    N = len(elements)
    circle_elements = elements * 2
    result = set()
    
    for length in range(1, N+1):
        for start in range(N):
            result.add(sum(circle_elements[start: start+length]))
    return len(result)

2. JS

function solution(elements) {
    const N = elements.length;
    const circleElement = elements.concat(elements);
    let result = new Set();
    
    for(let len = 1 ; len <= N ; len++){
        for(let s = 0 ; s < N ; s++){
            result.add(circleElement.slice(s, s + len).reduce((acc, cur) => acc + cur, 0));
        }
    }
    
    return result.size;
}

결과

---