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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. 원형 형태이므로 길이를 2배로 늘려준다.

2. 1부터 elements의 크기 갯수까지 구할 수 있는 모든 원소의 합을 구해준다.

3. set를 사용하여 중복을 제거하고 리스트의 크기를 반환한다.

def solution(elements):
    answer = 0
    new=elements*2 #1번
    total=[]
    for i in range(len(elements)): #2번
        for j in range(len(new)-i):
            num=sum(new[j:j+i+1])
            total.append(num)
    answer=len(list(set(total))) #3번
    return answer

원형이므로 0 1 2 3 4가 있을 때, 3개의 원소 합을 구하면 4 0 1도 가능하다는 점에서 문제에서 주언 elements의 길이를 2배로 늘리는 것이 핵심이었다.

이는 자료구조 수업에서 circular queue 부분에서 생각이 났었다.

하지만 해당 방법은 이중 for문을 사용하는 탓에 생각보다 시간복잡도가 너무 높아서 자칫하면 시간초과가 날 것 같다.

이보다 더 효율적인 방법을 모색해야겠다.