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

문제 설명

• 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 몇 가지인지 알아보고자 합니다.
• 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.
• 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
• 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 반환해주세요.
• 제한 사항
  • 3 ≤ elements의 길이 ≤ 1000
  • 1 ≤ elements의 원소 ≤ 1000
• 입출력 예시

elements	result
[7, 9, 1, 1, 4]	18

 

 

---

문제 풀이

def solution(elements):
    # 원형 수열을 처리하기 위해 elements 리스트를 두 배로 확장
    extended_elements = elements + elements
    unique_sums = set()  # 부분 수열의 합을 저장할 집합

    n = len(elements)  # 원래 수열의 길이

    # 부분 수열의 길이를 1부터 n까지 증가시키며 처리
    for length in range(1, n + 1):
        # 각 길이에 대해 시작 위치를 0부터 n-1까지 증가시키며 처리
        for start in range(n):
            # 부분 수열의 합을 계산
            part_sum = sum(extended_elements[start:start + length])
            # 집합에 합을 추가
            unique_sums.add(part_sum)

    # 중복을 제거한 부분 수열의 합의 개수를 반환
    return len(unique_sums)

 

문제 풀이 과정

1. 원형 수열에서 처음과 끝이 연결된 부분 수열을 쉽게 처리하기 위해 수열을 두 배로 확장한다. 
   [7,9,1,1,4,7,9,1,1,4]
2. 부분 수열의 길이를 1부터 원래 수열의 길이까지 변화시키면서 모든 가능한 시작 위치에서 부분 수열의 합을 계산한다.
3. 계산된 모든 부분 수열의 합을 집합(set)에 저장하여 중복을 제거한다.