연속 부분 수열 합의 개수
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
![](https://blog.kakaocdn.net/dn/xScZs/btrYGuWlEik/G8MG6tygkXTCEQ6lMmOwNk/img.png)
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 3 ≤ elements의 길이 ≤ 1,000
- 1 ≤ elements의 원소 ≤ 1,000
입출력 예elementsresult
[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]
풀이 및 소스코드
처음엔 시작인덱스에 개수를 더해 reduce로 합을 구한 후 Set<Int>에 추가하였지만 시간초과가 뜬다.
다른 언어들은 다 위와 같은 방법으로 하던데..?
실패[시간초과]
import Foundation
func solution(_ elements:[Int]) -> Int {
var result = Set<Int>()
let long = elements + elements
for many in 0..<elements.count{
var num = 0
for idx in 0..<elements.count{
//이 reduce부분에서 시간초과
result.insert(long[idx...idx+many].reduce(0){$0 + $1})
}
num = 0
}
return result.count
}
그래서 생각한 방법은 누적합이다.
요소가 [1, 2, 3] 3개라고 가정할 경우
1, 2, 3
1 + 2 = 3, 1 + 3, =4
2 + 3 = 5, 2 + 1 = 3
3 + 1 = 4, 3 + 2 = 5
1 + 2 + 3 = 6
1, 2, 3, 3, 4, 5, 3, 4, 5, 6
공백제거 -> 1, 2, 3, 4, 5, 6
8회의 많고 반복된 "+"연산이 필요하다.
누적합으로 할 경우 범위에 대한 reduce과정이 필요없다
1 + 2 = 3 -> 3 + 1 = 4
2 + 3 = 5 -> 5 + 1 = 6
3 + 1 = 4 -> 4 + 2 = 6
6회의 + 연산으로 모든 경우의 수를 구할 수 있다.
성공코드
import Foundation
func solution(_ elements:[Int]) -> Int {
//중복을 제거해야 하므로 Set<Int>를 사용
var result = Set<Int>()
//연속된 수열 %처리 해줘도 되지만 2배로 늘려줘도 된다.
let long = elements + elements
//시작 인덱스부터 원소의 개수만큼 누적되는 누적합을 result에 쌓아간다.
for idx in 0..<elements.count{
var num = 0
for offset in 0..<elements.count{
num += long[idx+offset]
result.insert(num)
}
num = 0
}
return result.count
}
//(0...4)