프로그래머스 연속 부분 수열 합의 개수 파이썬(python)

문제

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

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

제한 사항

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

---

풀이

풀이에서 elements * 2 해준 이유는 문제에서 리스트가 선형 구조라고 했기 때문에 index 값을 위해 해준것이다. 

직관적으로 봤을 때 완전 탐색으로 하게 된다면 O(N^3) 시간 복잡도가 걸려 시간초과가 날 것이다. 하지만 아래 코드에 완전 탐색으로 푼 풀이는 파이썬 슬라이싱덕분에 간신히 통과가 되는 코드이다. 보다 시간을 줄이기 위해서 생각한 방식이 DP 풀이 방법이다. 기본적인 점화식은 간단하다. 길이가 한 칸인 부분 수열의 합들이 초기 값이 될 것이고 길이가 두 칸인 수열의 합들은 길이가 한 칸인 합에서 한 칸을 추가로 더한 값이고 길이가 다섯 칸은 기존 네 칸에서 추가로 한 칸을 더한 경우이다. dp[i] = dp[i] + elements[dp[i]에 저장된 칸 보다 한 칸 나간 ix], 요소 값들을 더한 애들은 set() 집합에 넣어줘 중복 값을 제거시켜준다. 

dp 풀이

대충 그려보긴 했는데 이해가 안 가면 댓글 달아주시면 감사하겠습니다 ! 

 

# 완전 탐색
def solution(elements):
    answer = set()
    N = len(elements)
    elements = 2 * elements
    for limit in range(1, N+1):
        for i in range(N):
            answer.add(sum(elements[i:i+limit]))
    return len(answer)

# 위 풀이 코드 줄이기
def solution(elements):
    N = len(elements)
    elements = 2 * elements
    answer = [sum(elements[i:i + limit]) for limit in range(1, N + 1) for i in range(N)]
    return len(set(answer))

# dp 이용한 풀이 위 두가지 풀이보단 이 풀이가 가장 나아보임.
def solution(elements):
    N = len(elements)
    dp = elements[:]
    elements = 2 * elements
    answer = set(dp)
    for i in range(2, N):
        for j in range(N):
            dp[j] = dp[j] + elements[j+i-1]
            answer.add(dp[j])
    return len(answer) + 1

---

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

프로그래머스