[프로그래머스] 파괴되지 않은 건물 (Swift)

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

 

 

첫번째 보드에서 0,0 부터 3,4 까지의 칸에 모두 4씩 뺀 결과 = 두번째 보드

두번째 보드에서 2,0 부터 2,3 까지의 칸에 모두 2씩 뺀 경과 = 세번째 보드

이렇게 공격인지 회복인지의 타입과, 구간(시작점, 끝점), 더하거나 뺄 크기 가 N개 주어졌을 때

기존 보드에서 0보다 큰 칸의 개수를 구하는 문제

 

접근방법

누적합 문제였는데 처음에는 그냥 브루트포스마냥 다 일일이 빼는 코드를 짰다가. 시간초과나고

도저히 모르겠어서 이전에 풀었던 코드 보고 풀었다..

 

누적합의 핵심 원리는 처음 위치에 실제로 더하는 값을, 종료위치 바로 다음칸에 실제로 더하는 값의 보수를 넣어주고,

한칸씩 옆으로 이동하면서 이전 값을 내 위치에 더하는 것을 반복하면 구간의 처음 위치와 종료위치까지 처음 위치에 있었던 값이 들어가게 되는 원리임..

그래서 여러 구간의 값을 더하거나 빼야할 때 그 모든 구간을 반복하지 않아도 되고, 그 구간이 처음시작하는 점과 끝나는 점 다음 점에만 값을 넣어주면 되고, 마지막에 한번만 전체 구간을 돌아주면 되기 때문에 시간 복잡도가 N*M이 될 뻔한거를 N+M으로 줄여준다.

 

 

소스코드

import Foundation

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {    
    
    var result = 0
    let R = board.count
    let C = board[0].count
    
    var delboard = [[Int]](repeating: [Int](repeating: 0, count: C+1), count: R+1)
    
    for s in skill {
        let degree = s[0] == 1 ? -s[5] : s[5] 
        var r1 = s[1]
        var c1 = s[2]
        var r2 = s[3]
        var c2 = s[4]
        
        delboard[r1][c1] += degree // 누적합 시작점
        delboard[r1][c2+1] -= degree // 맨윗줄에서 누적합 종료지점
        delboard[r2+1][c1] -= degree // 맨왼쪽행에서 누적합 종료지점
        delboard[r2+1][c2+1] += degree // 종료지점의 값이 더해지는 것으로 인한 중복 피하기 값
    }
    
    // 가로방향 더하기
    for r in 0..<R {
        for c in 0..<C {
            delboard[r][c+1] += delboard[r][c]
        }
    }
    // 세로방향 더하기
    for c in 0..<C {
        for r in 0..<R {
            delboard[r+1][c] += delboard[r][c]
        }
    }
    
    // 최종 건물 내구도 구하기
    for r in 0..<R {
        for c in 0..<C {
            if board[r][c] + delboard[r][c] > 0 {
                result += 1
            }
        }
    }
    
    return result
}