백준 - 구간 합 구하기 5 (11660)

첫 번째 시도

import Foundation

let input = readLine()!.components(separatedBy: " ")
let N = Int(input[0])!, M = Int(input[1])!

var arr = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)
var sumArr = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)

// 배열에 원본 데이터 저장
for i in 1...N {
    let row = readLine()!.components(separatedBy: " ")
    for j in 1...N {
        arr[i][j] = Int(row[j-1])!
    }
}

// 1열 1행부터의 부분합 저장
for i in 1...N {
    for j in 1...N {
        sumArr[i][j] = sumArr[i][j-1] + sumArr[i-1][j] - sumArr[i-1][j-1] + arr[i][j]
    }
}

// 결과 출력
for _ in 0..<M {
    let data = readLine()!.components(separatedBy: " ")
    let x1 = Int(data[0])!, y1 = Int(data[1])!, x2 = Int(data[2])!, y2 = Int(data[3])!
    
    print(sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1])
}

분명 책에서 공부한 구현 방식대로 풀었는데 시간초과…

검색해보니 스위프트가 백준에서 원래 시간초과가 잘 나는 듯하다. 개빡치네…

두 번째 시도

import Foundation

let input = readLine()!.components(separatedBy: " ")
let N = Int(input[0])!, M = Int(input[1])!

var arr: [[Int]] =  Array(repeating: [0], count: N+1)
var sumArr = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)

// 배열에 원본 데이터 저장
for i in 1...N {
    let row = readLine()!.components(separatedBy: " ").map{ Int(String($0))! }
    arr[i] += row
}

// 1열 1행부터의 부분합 저장
for i in 1...N {
    for j in 1...N {
        sumArr[i][j] = sumArr[i][j-1] + sumArr[i-1][j] - sumArr[i-1][j-1] + arr[i][j]
    }
}

// 결과 출력
for _ in 0..<M {
    let data = readLine()!.components(separatedBy: " ").map{ Int(String($0))! }
    let (x1, y1, x2, y2) = (data[0], data[1], data[2], data[3])
    
    print(sumArr[x2][y2] - sumArr[x1-1][y2] - sumArr[x2][y1-1] + sumArr[x1-1][y1-1])
}

구글링해서 나온 결과 참고해서 고쳤는데도 시간 초과… 아니 왜..

해결 방법 및 알게 된 내용

• components(separatedBy:) 를 split(separator:) 로 바꿔주니까 위에 두 방법 모두 통과가 됐다…..😇 진짜 까다롭네..
• 한 줄 입력 받을 때 readLine()!.components(separatedBy: " ").map{ Int(String($0))! } 이런 식으로 고차함수를 사용하면 깔끔하게 형변환까지 할 수 있다.
• 여러 변수에 값 저장할 때는 튜플 사용! 이것도 공부했었는데 막상 적용해 볼 생각을 안 했었네..😅