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

문제

프로그래머스

입력

board: [[Int]] = r행 c열의 내구도
1 ≤ board의 행의 길이 (= N) ≤ 1,000
1 ≤ board의 열의 길이 (= M) ≤ 1,000
1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000

skill =[type, r1, c1, r2, c2, degree]
1 ≤ skill의 행의 길이 ≤ 250,000
skill의 열의 길이 = 6

type은 1 혹은 2입니다.
type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
(r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다
0 ≤ r1 ≤ r2 < board의 행의 길이
0 ≤ c1 ≤ c2 < board의 열의 길이
1 ≤ degree ≤ 500
type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
type이 2이면 degree만큼 건물의 내구도를 높입니다.
건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 
즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

출력

result: Int = 파괴되지않은 건물 개수

해석

1. 지속적으로 건물에게 가해진 영향을 더하고 빼므로 누적합을 의심할 수 있다.

2. 여기서 중요한 점은 1차원 누적합이 아니라 2차원 누적합이다.

 

2차원 누적합

 

적용되는 범위가 중요하다. skill의 범위는 (r1,c1) ~ (r2,c2) 까지를 모두 포함한다고 써있다.

만약 board가 3x3이라고 가정하면 누적합 배열은 이렇게 표현할 수 있다.

 

0	0	0
0	0	0
0	0	0

 

type = 2((회복)) r1 = 0, c1 = 0 , r2 = 1, c2 = 1, degree = 1 이면 다음 과 같이 변경된다.

 

[ 테이블 1 ] 

+1	0	-1
0	0	0
-1	0	+1

 

acc[r1][c1] += degree  , acc[r2+1][c2+1] += degree

acc[r1][c2+1] -= degree , acc[r2+1][c1] -= degree

 

이유는 뭘까 ?

 

영향을 받은건 r1 ~ r2 , c1 ~ c2 쪽인데 왜 r2+1과 ,c2+1 쪽이 영향을 받을까??

 

우리가 원하는 결과는 아래와 같은데

 

[ 테이블 2 ]

1	1	0
1	1	0
0	0	0

 

그거는 오른쪽에서 왼쪽으로 , 아래에서 위로 합쳐보면 알 수 있다. 

 

[ 테이블 1 ]을 먼저 오른쪽에서 왼쪽으로 누적합 해보자.

각 r에 대하여 acc[r][c] += acc[r][c-1] 진행해보자. 1 <= c < 3

 

[ 테이블 3 ]

1	1	0
0	0	0
-1	-1	0

 

다음은 [ 테이블 3 ]을 위에서 아래로 누적합을 진행해보자.

 

[ 테이블 4 ]

1	1	0
1	1	0
0	0	0

 

테이블 2번과 정확히 똑같은 결과가 도출된다. 불편한데 굳이 이렇게 하는 이유는 뭘까 ??

 

만약 영향이 가야하는 범위가 증가한다면  r*c의 모든 범위를 표시해야하고 그건 즉  (O(n^2)) 이 될 수 있다.

 

위와 같이 누적합을 이용하면 ((r1,c1)) , ((r1,c2+1)) , ((r2+1,c1)) , ((r2+1,c1+1))  4군데만 표시하고 필요할 때
더해주기만하면 되므로 효율성 자체가 다르다..

 

코드

import Foundation

 var acc: [[Int]] = []

func effect(_ s: [Int]) {
    
    let isHeal = s[0] == 2 ? true : false
    let r1 = s[1]
    let c1 = s[2]
    let r2 = s[3]+1
    let c2 = s[4]+1
    let degree = isHeal ? s[5] : -s[5]
    
    acc[r1][c1] += degree
    acc[r1][c2] -= degree
    acc[r2][c1] -= degree
    acc[r2][c2] += degree
}


func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {

    var board = board 
    let row = board.count
    let col = board[0].count
    acc = [[Int]](repeating: [Int](repeating: 0,count: col+1), count: row+1)
    
    for s in skill {
        effect(s)
    }
    
    //가로 누적합
    for r in 0..<row {
        for c in 1...col {
            acc[r][c] += acc[r][c-1]
        } 
    }

       //세로 누적합
    for c in 0..<col {
        for r in 1...row {
            acc[r][c] += acc[r-1][c]
        }
    }
    
 
    
    var result: Int = 0
    
    for r in 0..<row {
        for c in 0..<col {
        
            if board[r][c] + acc[r][c] > 0 { 
                result += 1
            }
            
        }
    }
    
    
    return result
}