[프로그래머스 Lv2, python]- 연속 부분 수열

 

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

프로그래머스

def solution(ele):
    li=[]
    idx=2 # 연속 부분 수열 길이
    le=len(ele) # ele의 길이 저장
    for a in ele: # 길이1인 연속 부분 수열
        if a not in li:
            li.append(a)
    while(idx<le): # 연속 부분 수열 길이가 ele의 길이보다 작아야함
        for a in range(0,le): 
            cnt=0 # idx+a가 le보다 커졌을때 어느정도 차이나는지.
            su=0 # 연속 부분 수열의 합
            if(le-a<idx):
                cnt=idx-(le-a) 
            if(cnt!=0): 
                su=sum(ele[:cnt])
                su+=sum(ele[a:])
            else:
                su+=sum(ele[a:a+idx])
            li.append(su)
        idx+=1
    li.append(sum(ele)) # 다 합친것은 while내에서 포함이안되어 따로 해줌
    li=set(li) # 중복 제거
    return len(li)

위의 풀이는 통과되었지만 시간복잡도가 조금 있었다.

아래는 다른분의 풀이인데, 하나를 기준으로 길이를 점차 늘려가며 집합에 추가해주었다. 

def solution(elements):
    ll = len(elements) 
    res = set()

    for i in range(ll):
        ssum = elements[i]
        res.add(ssum)
        for j in range(i+1, i+ll):
            ssum += elements[j%ll]
            res.add(ssum)
    return len(res)