[programmers/py] 연속 부분 수열 합의 개수

연속 부분 수열 합의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/131701

문제 설명

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이

1. 중복 제거를 위해 set을 선언
2. [1,2,3,4,5]
   2-1. i=0, el[0] = 1
   2-2. j=1~i+len(arr)을 통해 원형을 구현
   2-3. i=0, j=1~5일 때 반복문을 돌면 결국 i에 대한 모든 경우의 합을 구할 수 있다.

el[0] 1
el[j] = 2 3 4 5
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5가 실행되어 경우의 수를 구해줌

def solution(elements):
    answer = set()
    l = len(elements)
    
    for i in range(l):
        s = elements[i]
        answer.add(s)
        for j in range(i+1, i+l):
            s += elements[j%l]
            answer.add(s)
    
    return len(answer)