[백준(BOJ)] 11659 구간 합 구하기 4 - 스위프트(Swift)

[Silver III] 구간 합 구하기 4 - 11659

문제 링크

성능 요약

메모리: 76204 KB, 시간: 196 ms

분류

누적 합

문제 설명

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

풀이

i)

처음에는 해당 값들을 전부 받은 뒤 인덱스가 같은 경우를 제외한 뒤, for문을 통해 합을 더하고, 출력하는 형식으로 생각했습니다.

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

for _ in 0..<m {
    let ij = readLine()!.split(separator: " ").map { Int($0)! }
    let (i, j) = (ij[0], ij[1])
    var sum = 0
    if i == j { // 만약 인덱스가 같으면 -> 그냥 하나만 출력하면 됨
        print(num[i - 1])
    } else {
        for k in i - 1..<j {
            sum += num[k]
        }
        print(sum)
    }
}

→ 시간 초과

 

위 방식으로 풀게되면 O(n^2)의 시간 복잡도가 나타나기 때문에 시간 초과가 나타났습니다.

 

ii)

해당 문제는 누적 합을 통해 구현해야 문제가 해결됩니다.

 

배열에 누적 합에 대한 값들을 저장한 후, 조건에 맞는 범위만큼을 지정하여 값을 제거합니다.

 

그림으로 보면 다음과 같습니다.

 

누적 합 설명

 

코드로 보면 다음과 같습니다.

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

// 누적 합
var prefixNum = Array(repeating: 0, count: num.count)
prefixNum[0] = num[0]
for i in stride(from: 1, to: num.count, by: 1){
    prefixNum[i] += (num[i] + prefixNum[i - 1])
}

var ans = ""

for _ in 0..<m {
    let ij = readLine()!.split(separator: " ").map { Int($0)! }
    let (i, j) = (ij[0], ij[1])
    var sum = 0
    
    if i == j { // 만약 인덱스가 같으면 -> 그냥 하나만 출력하면 됨
        sum = num[i - 1]
    }
    else if i != 1 {    // 두 번째 이상부터 -> 누적합의 차이
        sum = prefixNum[j - 1] - prefixNum[i - 2]
    } else {    // 첫 번째부터 시작한다면 -> j - 1 인덱스 출력
        sum = prefixNum[j - 1]
    }
    
    ans += "\(sum)\n"
    
}
print(ans)

 

누적 합에 대한 내용은 조만간 다룰 예정입니다.