[swift] 백준 - 11659번: 구간 합 구하기 4

11659번: 구간 합 구하기 4

---

정답 풀이

let NM = readLine()!.split(separator: " ").map { Int($0)! }
let arr = readLine()!.split(separator: " ").map { Int($0)! }
var sumArr = Array(repeating: 0, count: arr.count+1)

for i in 0..<arr.count {
    sumArr[i+1] = sumArr[i] + arr[i]
}

for _ in 0..<NM[1] {
    var i = readLine()!.split(separator: " ").map { Int($0)! }
    print(sumArr[i[1]] - sumArr[i[0]-1])
}

 

해당 문제는 누적합(prefix sum) 문제다.

 

해당문제는 N이 최대 10만, M이 최대 10만이 입력될 수 있어

10만 * 10만 = 1억 번을 아득히 넘기에 N^2인 완전탐색은 안되고

어떻게든 10만을 O(log n)이나 O(1)로 풀어내야 한다.

 

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

해당 코드는 최악의 경우 10만 * 10만이기에 시간초과가 난다.

 

좋은 방법은 미리 배열을 만들어 두고 누적되는 합을 저장시켜 놓는 건데

예시문제로 설명하자면

누적합을 구해야 하는 배열(arr) [5,4,3,2,1]이 주어진다.

 

 첫 번째로 arr의 count에 + 1만큼 0으로 채워진 sumArr배열을 만들어줬다.

sumArr = [0,0,0,0,0,0] 형태가 된다.

 

for i in 0..<arr.count {
    sumArr[i+1] = sumArr[i] + arr[i]
}

해당 코드는 index를 이용해 누적되는 합을 sumArr에 저장시켜 준다.

 

해당 반복이 끝난다면 sumArr는

[0,5,9,12,14,15]로 누적합을 저장하는 배열이 만들어진다.

 

해당 반복은 최대 10만이 될 것이다.

 

다음으로, 주어진 문제를 풀기 위해 M만큼 반복하게 되는데

중첩 for문이었다면 N * M이었겠지만

지금은 미리 만들어둔 배열 덕에 N + M이 됐다.

 

10만 번을 따로돌고 10만번을 따로 돌아

최대 20만 번의 반복 횟수로 줄었다.

 

for _ in 0..<NM[1] {
    var i = readLine()!.split(separator: " ").map { Int($0)! }
    print(sumArr[i[1]] - sumArr[i[0]-1])
}

M만큼 반복하며 주어진 입력값 범위의 합을 구하기 위해서

해당 코드로 구현했다.

 

---