[Swift 알고리즘] 백준 2559 수열

○

누적 합 Silver3

백준 2559번 수열

문제
매일 측정한 온도(정수)의 수열이 주어질 때, 연속적인 며칠 동안의 온도 합이 가장 큰 값을 계산
입력
- N은 온도를 측정한 전체 날짜의 수. 2 ≤ N ≤ 100,000
- K는 합을 구하기 위한 연속적인 날짜의 수. 1 ≤ K ≤ N
- 온도를 나타내는 N개의 정수는 모두 -100 이상 100 이하

구현 까지는 18분 걸렸고, 예외 처리(?) 9분 해서 총 27분 걸림

예외처리랄것도 없는데 result 값을 처음에 0으로 초기화 해서 틀렸다고 뜸. 

모든 온도가 음수일 경우, max() 해주면 result 값으로 0이 그대로 출력되는 문제,, 

처음부터 result 값을 0이 아니라 가능한 합의 값으로 설정해주는 것이 중요. 

 

1. 누적 합 방식으로 구현 : 76152KB 36ms

let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, k) = (nk[0], nk[1])
let arr = readLine()!.split(separator: " ").compactMap { Int($0) }

//1. 누적합 76152KB 36ms
var prefixSum = Array(repeating: 0, count: n+1)
for i in 1...n {
    prefixSum[i] = prefixSum[i-1] + arr[i-1]
}
var result = prefixSum[k] - prefixSum[0]
for i in k...n {
    result = max(result, prefixSum[i] - prefixSum[i-k])
}
print(result)

 

2. 슬라이딩 윈도우 76152KB 36ms

참고용으로 그냥 알아둬도 될듯 

배열을 돌면서 합의 앞 인자는 빼고, 뒷 인자는 추가해 최대와 비교해준다. 간결하구만

//2. 슬라이딩 윈도우 76152KB 36ms 
var window = arr.prefix(k).reduce(0, +)
var result = window
for i in k..<n {
    window += arr[i] - arr[i-k]
    result = max(result, window)
}
print(result)