문제

문제 링크

접근

• 처음에는 단순히 문제의 순서에 따라 배열을 채웠다. O(n) 수준의 시간 복잡도이지만, 명령어 수가 많아서 효율성 테스트 0점이 나온당,,ㅠ
• 아무리 생각해도 해답이 안 떠올라서, 2차원 누적합이라는 키워드를 얻고 풀이하였다.
• 일반적인 2차원 배열에서의 누적합 방식 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]으로 풀이하였다.
• 각각 칸의 변화값은 도함수와 같이 생각하여 영역 좌상단, 우하단 아래에 변화값을 표시하고, 좌하단 아래, 우상단 오른쪽에 변화값 복구값을 표시하였다.
• 마지막에 누적합과 변화값을 더하여 붕괴 여부를 판단하였다.

풀이

import java.util.*;

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int[][] points = new int[board.length + 1][board[0].length + 1];
        int[][] sums = new int[board.length][board[0].length];
        int H = board.length, W = board[0].length;
        int answer = 0;
        
        for (int[] s : skill) {
            int e = s[0] == 1? -1 * s[5] : s[5];
            points[s[1]][s[2]] += e;
            points[s[1]][s[4]+1] += -1 * e;
            points[s[3]+1][s[2]] += -1 * e;
            points[s[3]+1][s[4]+1] += e;
        }
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                int leftTop = i > 0 && j > 0? sums[i-1][j-1] : 0;
                int top = i > 0? sums[i-1][j] : 0;
                int left = j > 0? sums[i][j-1] : 0;
                
                sums[i][j] = top + left - leftTop + points[i][j];
                if (sums[i][j] + board[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
}