skill 배열의 구조
처음에는 시뮬레이션 문제처럼 문제가 말하는대로 그대로 따라하려 해보았다
하지만 그렇게 되면 O(1000x1000x250000)으로 시간초과가 난다
그래서 누적합을 사용하는 방법을 찾아내었다.
만약 아래처럼 r1=1, c1=1, r2=2, c2=2인 곳에 5를 채워야한다면
(1,1)에 5를 쓰고 (2,3)에 -5, (3,2)에 -5, (3,3)에 5를 채워놓고
가로 세로 누적합을 처리해주면 원하는 2차원 배열을 얻을 수 있다
따라서 0으로 채워진 N*M배열에 skill배열을 이용해 숫자를 채우고 한 번에 누적합 처리를 해주면 효율성 높게 답을 구할 수 있다.
public class Solution {
public int solution(int[][] board, int[][] skill) {
int n = board.length;
int m = board[0].length;
int[][] zero = new int[n+1][m+1]; // 1씩 크기 크게
// 누적합 전처리
for (int[] row : skill) {
int r1 = row[1];
int c1 = row[2];
int r2 = row[3];
int c2 = row[4];
int degree = row[0] == 2 ? row[5] : -row[5];
zero[r1][c1] += degree;
zero[r1][c2+1] -= degree;
zero[r2+1][c1] -= degree;
zero[r2+1][c2+1] += degree;
}
// 가로 누적합
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
zero[i+1][j] += zero[i][j];
}
}
// 세로 누적합
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
zero[i][j+1] += zero[i][j];
}
}
// 정답 구하기
int answer = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(zero[i][j] + board[i][j] > 0) answer++;
}
}
return answer;
}
}
문제의 시간복잡도가 매우 커진다면 누적합 또는 이분탐색을 생각하자