연속 부분 수열 합의 개수

문제 설명

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

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

제한사항

• 3 ⇐ elements 의 길이 ⇐ 1,000
• 1 ⇐ elements 의 길이 ⇐ 1,000 brute-force 로 접근해도 총 계산 수가 $10^6$ 정도로 통과할 수 있어 보인다.

풀이

첫번째 접근

연속된 수열이라고 해서 복잡해 보일 수 있지만 리스트의 가장 마지막 수에서 부터 계산할 때 리스트의 갯수만큼의 원소를 추가로 뒤에 붙혀서 부분 수열을 만들기 때문에 처음 리스트를 2개로 늘리면 해결 가능 하다.

첫번째 나올 수를 기준으로 모든 경우의 수를 찾아 더해 리턴 하는 방식으로 접근했다.

def solution(elements):
	nums=elements*2 # 본래의 리스트를 두개 붙혀준다.
	res=set() # set으로 지정하여 중복된 수가 없게 한다.
	
	for i in range(len(elements)): # 본래의 길이만큼 루프를 돌리며 리스트의 시작 위치를 표시한다.
		for j in range(i+1,len(elements)+1+i): # 시작되는 부분부터 최대 가능한 가짓수를 모두 구한다.
			res.add(sum(nums[i:j])) # 리스트 원소의 모든 합을 구하여 결과에 추가한다.
	return len(res)