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

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

프로그래머스

 

문제설명

 

 

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

 

 

 

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

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

 

문제 해결 방법

 

deque의 maxlen 속성을 이용하여 문제를 해결했다. 

deque의 maxlen 속성은 deque를 생성할때 maxlen에 값을 주면 해당 값만큼의 크기의 deq를 만들 수 있는 속성이다. 

 

만약 사용자가 해당 deque에 maxlen이상의 값을 추가하면 deq에 있는 맨 왼쪽의 값부터 삭제한다. 

(appendleft()를 할 경우, 맨 오른쪽의 원소가 삭제되고 맨 왼쪽에 값이 추가됨)

 

문제에서는 연속된 값의 길이가 1부터 elements의 크기 까지일 수 있다. 

따라서 해당 경우를 헤아려 가며 deq를 만들어주고 deq 요소의 값을 합해준 후, 해당 값을 하나의 리스트에 넣었다. 

 

중복값에 대한 처리는 set으로 해줬다. 

 

코드 구현

 

from collections import deque

def solution(elements):
    answer = 0
    a = []
    for i in range(1,len(elements)+1) :
        deq = deque(maxlen=i)
        
        for i in elements * 2 :
            deq.append(i)
            a.append(sum(deq))
            
    
            
        
    
    return len(set(a))

 

 

시간/공간 복잡도

 

최악의 경우 O(N^2)

 

 

최적화 및 개선 / 어려웠던 점

 

사실 이 문제를 3중 for문으로 풀었는데 아니나 다를까, 테스트 케이스 5번부터 끝까지 시간초과가 났다. 

 

근데 아무리 생각해봐도 3중으로 for문을 사용하지 않으면 문제를 풀 수 있는 방법을 떠올릴 수 없었다. 

 

힌트를 얻어 문제를 풀었다. deque에 maxlen이라는 속성이 있는지 처음 알았다. 최고다!