문제 설명
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
제한 사항
- 3 ≤
elements의 길이 ≤ 1,000 - 1 ≤
elements의 원소 ≤ 1,000
입출력 예
| elements | 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]
풀이
배열의 포인터를 0, 1, 2, ... len(elements)-1 만큼 이동하면서, 포인터 + 1, 포인터 + 2, ..., 포인터 + len(elements) 만큼 슬라이스 해 오면 각각 길이가 1인 배열, 길이가 2인 배열, ..., 길이가 len(elements)인 배열이 만들어지게 됩니다. 이 배열의 합을 구하고, set에 넣은 뒤(중복 합이 있을 수도 있으므로) 이 set의 길이가 답이 됩니다.
다만 문제에서 제시하는 것은 원형 수열입니다. 수열의 끝에 다다르면 다시 처음으로 돌아가게 되는 것이죠.
저는 수열 뒤에 똑같은 수열을 이어 붙여줌으로써, 그냥 포인터를 쭉 증가시켜도 순환적으로 접근하는 것과 동일한 결과를 얻도록 하였습니다.
코드
def solution(elements):
answer = 0
numberSet = set()
elementLen = len(elements)
elements = elements * 2
for i in range(elementLen) :
for j in range(elementLen) :
numberSet.add(sum(elements[j:j+i+1]))
answer = len(numberSet)
return answer의문이 드는 점, 개선해야할 점은 댓글로 남겨주세요.
감사합니다 😽
