문제 확인
나의 풀이
- 성분의 개수($n$)을 늘려가며 부분 수열을 구성하면 되는 문제다.
- 끝점의 index가 범위를 초과할 경우를 처리해주는 것이 중요하다.
- 범위 초과 시 위 그림과 같이 표현할 수 있기 때문에 각 수열을 나눠서 합했다.
def solution(elements):
sum_unique = set()
# 성분 개수
for n in range(len(elements)):
# 시작점
for i in range(len(elements)):
# 배열의 길이 초과할 경우
if n + i > len(elements):
e_sum = sum(elements[i:]) + sum(elements[:i + n - len(elements)])
else:
e_sum = sum(elements[i:i + n])
sum_unique.add(e_sum)
return len(sum_unique)
다른 사람 풀이
회전 큐를 사용한 풀이
- 매 회전 마다 부분 합을 따로 구하게 되면, 결국 전체 부분합 경우를 모두 고려할 수 있다.
deque.rotate(1) == list[i:] + list[:i]
from collections import deque
def solution(elements):
answer = set()
elements = deque(elements)
for j in range(len(elements)):
elements.rotate(1)
for i in range(1,len(elements)):
answer.add(sum(list(elements)[:i]))
answer.add(sum(elements))
return len(answer)
범위 초과하는 리스트 인덱싱 쉽게 하는 방법
- 리스트를 연결하면 된다!
def solution(elements):
result = set()
elementLen = len(elements)
# [7, 9, 1, 1, 4, 7, 9, 1, 1, 4]
elements = elements * 2
for i in range(elementLen):
for j in range(elementLen):
result.add(sum(elements[j:j+i+1]))
return len(result)
참고