문제

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;
    }
}

느낀점

문제의 시간복잡도가 매우 커진다면 누적합 또는 이분탐색을 생각하자