누적합은 1차원 -> O(n), 2차원 -> O(n^2)의 시간 복잡도를 가진다.
class Solution {
public int solution(int[][] board, int[][] skill) {
int N = board.length;
int M = board[0].length;
int[][] sum = new int[N + 1][M + 1];
for (int[] info : skill) {
int y1 = info[1];
int x1 = info[2];
int y2 = info[3];
int x2 = info[4];
int power = info[5] * (info[0] == 1 ? -1 : 1);
sum[y1][x1] += power;
sum[y1][x2 + 1] += power * -1;
sum[y2 + 1][x1] += power * -1;
sum[y2 + 1][x2 + 1] += power;
}
for (int y = 1; y < N; y++) {
for (int x = 0; x < M; x++) {
sum[y][x] += sum[y - 1][x];
}
}
for (int x = 1; x < M; x++) {
for (int y = 0; y < N; y++) {
sum[y][x] += sum[y][x - 1];
}
}
int answer = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
if (board[y][x] + sum[y][x] > 0) {
answer++;
}
}
}
return answer;
}
}