프로그래머스 링크

코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int height = board.length;
        int width = board[0].length;
        int r2, c2, r1, c1;

        int[][] sum = new int[height + 1][width + 1];
        for (int[] s : skill) {
            int degree = (s[0] == 1 ? -s[5] : s[5]);
            r1 = s[1];
            r2 = s[3];
            c1 = s[2];
            c2 = s[4];
            
            sum[r1][c1] += degree;
            sum[r1][c2 + 1] -= degree;
            sum[r2 + 1][c1] -= degree;
            sum[r2 + 1][c2 + 1] += degree;
        }

        operate(height, width, sum);

        for (int r = 0; r < height; r++) {
            for (int c = 0; c < width; c++) {
                if (board[r][c] + sum[r][c] > 0) {
                    answer++;
                }
            }
        }
        return answer;
    }

    private void operate(int height, int width, int[][] sum) {
        for (int r = 0; r < height + 1; r++) {
            for (int c = 1; c < width + 1; c++) {
                sum[r][c] += sum[r][c - 1];
            }
        }

        for (int c = 0; c < width + 1; c++) {
            for (int r = 1; r < height + 1; r++) {
                sum[r][c] += sum[r - 1][c];
            }
        }
    }
}

풀이

핵심 제한사항
1 ≤ board의 행의 길이 (= N) ≤ 1,000
1 ≤ board의 열의 길이 (= M) ≤ 1,000
1 ≤ skill의 행의 길이 ≤ 250,000

skill마다 board의 요소를 하나하나 바꿔주는 방식은 비효율적인 방식이다. N x M x skill의 행의길이의 최대값이 억단위를 훌쩍 넘어가기 때문이다.

skill을 하나하나 전부 돌아야 하는 것은 피할 수 없다. skill마다 board를 하나하나 바꿔주는 방식을 개선해야 한다. skill마다 4개의 꼭지점에만 값을 저장하고, 한번에 연산 해주는 방식을 사용하면 해결할 수 있다.