연속 부분 수열 합의 개수 (파이썬)

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

프로그래머스

 

첫 접근 방법

## 시간초과 코드
def solution(elements):
    lst = []
    elen = len(elements)
    elements += elements
    for i in range(elen):
        for j in range(elen):
            tmp = 0
            for k in range(i, j + i + 1):
                tmp += elements[k]
            lst.append(tmp)
    return len(set(lst))

3중 for문을 이용해 n^3 시간 복잡도가 형성되어 몇 개의 테스트케이스에서 시간초과가 뜨게 되었다.

 

수정 (elements[i:i+length])이용

# 수정 sum(elements[i:i+length]) 이용
def solution(elements):
    elen = len(elements)
    elements += elements
    sums = set()

    for length in range(1, elen + 1):
        for i in range(elen):
            sums.add(sum(elements[i:i+length])) ## 핵심 (이게되네)

    return len(sums)

파이썬 다운 코드인듯하다. set으로 일단 중복을 처리해 주고, i:i+length로 구간 합을 계산해 준다.