[프로그래머스] 연속 부분 수열(python)

문제

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

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한조건

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

 

 입출력 예

 

 

 

풀이

 이 문제는 원형으로 연속된 수열이 존재할 때 n개씩 연속하는 부분 수열로 나누었을 때 합을 구하고, 그 합이 총 몇개인지를 구하는 문제입니다. 

예를 들어 [7,9,1,1,4] 수열에서 2개씩 연속하는 부분 수열로 나누게 된다면 [7,9], [9,1], [1,1], [1,4], [4,7] 와 같이 5개로 나누어지고, 3개씩 연속하는 부분 수열로 나누게 되면 [7,9,1], [9,1,1], [1,1,4], [1,4,7], [4,7,9] 와 같이 5개로 나누어 지게 됩니다. 여기서 부분 수열로 나누기 위해서 0번째부터 n번째까지 부분수열로 나누어 주고, 맨뒤의 값을 맨앞으로 가져와서 0번째부터 n번째까지 부분수열로 나누는 과정을 반복하는 방법이 있다는 규칙을 알게 되었습니다.

이를 구현하기 위해 deque를 이용하여 맨뒤의 값을 맨앞으로 가져오는 과정을 반복하면서, deque의 값을 n개씩 슬라이싱 하는 과정을 반복하여 풀이를 진행하였습니다. 

 

1. deque의 0번째부터 슬라이싱하여 합을 구하고 answer에 값을 더해준다.

2. rotate를 통해 맨뒤의 값을 맨앞으로 이동한다.

3. 이중 for 문을 통해 2의 과정을 요소의 수만큼 반복(중복되는 모든 합이 다 나옴) 및 슬라이싱 할 개수를 1개부터 1씩 늘리며 반복한다.

5. 위의 과정이 모두 끝난 후, 중복되는 값을 제거해주고, 리스트의 길이를 리턴한다.

 

from collections import deque
import itertools

def solution(elements):
    answer = []
    temp = deque(elements)
    
    for i in range(len(elements)):
        for j in range(len(elements)):
            result = sum(itertools.islice(temp,0,i+1))  # 합을 구할 만큼 슬라이싱
            answer.append(result)
            temp.rotate(1)                              # rotate를 통해 맨 뒤의 값 앞으로 가져옴
    
    answer = list(set(answer))
    return len(answer)

 

 

위와 같이 풀이를 진행하여 모든 테스트 케이스를 통과하는 것을 확인할 수 있습니다.

 

추가로 다른 풀이들을 참고해보니 deque를 사용하지 않고 elements 리스트를 2번 반복하여 합을 구한 후 중복을 제거하는 방법도 있으니 해당 방법으로도 풀이를 해보시면 좋을 것 같습니다.