[Programmers] 연속 부분 수열 합의 개수 바로가기
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements
가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
elements
의 길이 ≤ 1,000elements
의 원소 ≤ 1,000elements | result |
---|---|
[7,9,1,1,4] | 18 |
입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]
sum()
함수를 이용하면 시간 초과
문제가 발생할 수 있다.sum()
함수를 이용하여 구한 후 이후의 값은 첫번째 원소를 빼고 마지막 원소를 더하는 방식으로 부분 수열의 합을 구하였다.[7, 9, 1, 1, 4]
에서 길이가 3
인 부분 수열을 구하는 방법은 아래와 같다.7 + 9 + 1 = 17
)을 구한다.17
)에서 첫번째 원소(7
)를 빼고 뒤의 원소(1
)를 더하는 방식(17 -7 + 1 = 11
)을 적용하여 구한다.9 + 1 + 1 = 11
)의 결과와 위의 방식의 결과(17 -7 + 1 = 11
)는 같은 값을 갖는다.answer = set([sum(elements)])
set
) 자료구조를 생성for length in range(1,N):
total = sum(elements[:length])
start, end = 0, length
for _ in range(N):
total += elements[end] - elements[start]
start, end = start+1, (end+1)%N
answer.add(total)
1
부터 N-1
까지의 합을 계산하기 위해 반복문을 실행한다.index = 0
)부터 부분 수열의 길이(length
)에 해당하는 원소까지의 합(total
)을 구한다.start
)와 마지막 원소의 인덱스(end
)를 초기화한다.length
)에 상관없이 원형 수열에서 구할 수 있는 모든 부분 수열의 개수는 원형 수열의 길이(N
)과 같다.N
번 반복하는 반복문을 실행한다.total
)에서 첫번째 원소(elements[start]
)의 값만큼 감소시키고 마지막 원소(elements[end]
)의 값만큼 증가시킨 값은 원형 수열에서 시계방향으로 이동하는 것과 같다.total
)을 answer
에 추가하고 첫번째 원소의 인덱스(start
)와 마지막 원소의 인덱스(end
)를 갱신한다.def solution(elements):
answer = set([sum(elements)])
N = len(elements)
for length in range(1,N):
total = sum(elements[:length])
start, end = 0, length
for _ in range(N):
total += elements[end] - elements[start]
start, end = start+1, (end+1)%N
answer.add(total)
return len(answer)