[Swift 알고리즘] 백준 11659 구간 합 구하기 4

△

누적 합 Silver3

백준 11659번 구간 합 구하기 4

첫번째 시도 - 시간초과 

단순하게 받아온 배열 저장 후, 횟수 m만큼 for문을 돌려 합을 구해주는 방법

횟수 m의 범위가 10만이기 때문에, 최악의 경우 O(n^2) 10만 x 10만 으로 시간초과가 뜬다. 

let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let m = nm[1]
let arr = readLine()!.split(separator: " ").compactMap { Int($0) }

for _ in 0..<m {
    let interval = readLine()!.split(separator: " ").compactMap { Int($0) }
    var sum = 0
    for i in (interval[0] - 1)..<interval[1] {
        sum += arr[i]
    }
    print(sum)
}

 

누적합 Prefix Sum - 76200KB 268ms

누적 합 방식으로 풀어주면 O(n) 으로 통과할 수 있다. 

처음 누적합 배열 저장할 때만 O(n) 이 걸리고, 구간 합을 구할 때에는 계속 더해줄 필요 없이 마이너스 연산만으로 해결 가능 O(1)

O(10만 x 1)

let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, m) = (nm[0], nm[1])
var arr = [0]
arr.append(contentsOf: readLine()!.split(separator: " ").compactMap { Int($0) })

for i in 1...n {
    arr[i] += arr[i-1]
}

for _ in 0..<m {
    let interval = readLine()!.split(separator: " ").compactMap { Int($0) }
    print(arr[interval[1]] - arr[interval[0] - 1])
}

누적 합 구할 때 배열이 index 1 부터 저장을 해주면 연산이 편해서 위와 같이 [0] 에다가 append 하는 형식으로 풀었는데,

아래처럼 그냥 배열 받아와서 분기처리 해줘도 상관없음

let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, m) = (nm[0], nm[1])
var arr = readLine()!.split(separator: " ").compactMap { Int($0) }
for i in 1..<n {
    arr[i] += arr[i-1]
}

for _ in 0..<m {
    let interval = readLine()!.split(separator: " ").compactMap { Int($0) }
    if interval[0] == 1 {
        print(arr[interval[1] - 1])
    } else {
        print(arr[interval[1] - 1] - arr[interval[0] - 2])
    }
}

다음과 같이 아예 prefixSum 배열을 새로 만들어서 풀어도 사용 메모리는 같더라? O _ O

그렇다면 요 방법이 젤 깔꼼한듯

let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, m) = (nm[0], nm[1])
var arr = readLine()!.split(separator: " ").compactMap { Int($0) }
var prefixSum = Array(repeating: 0, count: n + 1)

for i in 1...n {
    prefixSum[i] = prefixSum[i-1] + arr[i-1]
}

for _ in 0..<m {
    let interval = readLine()!.split(separator: " ").compactMap { Int($0) }
    print(prefixSum[interval[1]] - prefixSum[interval[0] - 1])
}