[Swift][누적합][LV_3] 파괴되지 않은 건물

요구능력 : 누적합

 

코드설명 : 

 

카카오테크블로그에 정말 설명이 쉽게 잘되어있습니다.

 

사실상 똑같은 유형의 문제를 접해보지 않는이상 이 문제는 풀기 어려운것같습니다.

누적합을 공부하고 이 문제를 풀어보면서 너무 많이 돈다고 생각했는데,

알고보니 변화하는 부분을 한번에 다 체크해주고 누적합을 한번에 구하는것이었습니다.

 

후기 : 개념을 알고있으면 쉬운문제인데 개념을 모른다면 효율성테스트를 절대 통과할 수 없다.

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    let n = board.count
    let m = board[0].count
    var count = 0
    var preArr = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
    for i in skill{
        let type = i[0]
        let degree = type == 1 ? -i[5] : i[5]
        let r1 = i[1]
        let c1 = i[2]
        let r2 = i[3]
        let c2 = i[4]
        
        preArr[r1][c1] += degree
        preArr[r1][c2 + 1] -= degree
        preArr[r2 + 1][c1] -= degree
        preArr[r2 + 1][c2 + 1] += degree
    }
    //왼쪽에서 오른쪽 누적합
    for i in 0..<preArr.count{
        for j in 0..<preArr[i].count{
            if j + 1 < preArr[i].count{
                preArr[i][j + 1] += preArr[i][j]
            }
            
        }
    }
    //위쪽에서 아래쪽 누적합
    for i in 0..<preArr.count{
        for j in 0..<preArr[i].count{
            if j + 1 < preArr.count{
                preArr[j + 1][i] += preArr[j][i]
            }
            
        }
    }
    
    //합치기
    for i in 0..<n{
        for j in 0..<m{
            preArr[i][j] += board[i][j]
            if preArr[i][j] > 0 {
                count += 1
            }
        }
    }
    
    return count
}