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

🔒 문제

문제 링크

🔑 해결 아이디어

누적 합을 사용하는 문제다.
누적합이란?

다만, 이번 문제의 경우 2차원 배열에서의 누적합이기 때문에 column 단위로 한번, row 단위로 한번 도합 두번에 걸쳐 누적합 배열을 구해야 한다.

💻 소스코드

class Solution {
    int[][] operation;
    int building = 0;
    public int solution(int[][] board, int[][] skill) {
        operation = new int[board.length][board[0].length];
        
        for(int s = 0; s<skill.length; s++){
            operate(skill[s][0], skill[s][1], skill[s][2], skill[s][3], skill[s][4], skill[s][5]);
        }
        calc(board);
        
        return building;
    }
    
    public void operate(int type, int x1, int y1, int x2, int y2, int degree){
        if(type == 2)
            degree *= -1;
        this.operation[x1][y1] -= degree;
        if(y2 + 1< operation[0].length)
            this.operation[x1][y2+1] += degree;
        
        if(x2 + 1 < operation.length){
            this.operation[x2+1][y1] += degree;
            if(y2 + 1< operation[0].length)
                this.operation[x2+1][y2+1] -= degree;
        }
    }
    
    public void calc(int[][] board){
        for(int y = 0; y<operation[0].length; y++){
            for(int x = 1; x<operation.length; x++)
                operation[x][y] += operation[x-1][y];
        }
        
        for(int x = 0; x<operation.length; x++){
            for(int y = 0; y<operation[0].length; y++){
                if(y != 0)
                    operation[x][y] += operation[x][y-1];
                board[x][y] += operation[x][y];
                if(board[x][y] > 0)
                    building++;
            }
        }
    }
    
}

참고 설명

프로그래머스 유저의 접근 방법 설명