[프로그래머스] 파괴되지 않은 건물 - JAVA

in Algorithm on 기타

https://school.programmers.co.kr/learn/courses/30/lessons/92344

풀이

N X M 크기의 영역이 주어지고, 각 영역을 사각형 크기의 영역을 정해 일정 수를 더하고 빼주게 된다.

누적합을 이용하는 문제였다.

(a, b) 부터 (c, d) 까지의 사각형에 5씩 더해주기 위해서는

arr[a][b] += 5
arr[a+1][b+1] += 5
arr[a][b+1] -= 5
arr[a+1][b] -= 5

위처럼 더해주면 된다. 이렇게 수를 저장한 뒤 행마다 왼쪽에서 오른쪽으로 누적합해주고,

열마다 위에서 아래로 누적합해주면 된다.

[5, 0, 0, -5] [0, 0, 0, 0] [0, 0, 0, 0] [-5, 0, 0, 5]

이렇게 적은 뒤 누적합을 수행하면

[5, 5, 5, 0] [5, 5, 5, 0] [5, 5, 5, 0] [0, 0, 0, 0]

이렇게 원하는 영역에 누적합이 된 것을 확인할 수 있다.

메모리: 217MB

시간: 40.38ms

언어: Java 11

코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int N = board.length;
        int M = board[0].length;

        int[][] sum = makeSumArr(skill, N, M);

        int answer = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(board[i][j] + sum[i][j] > 0) {
                    answer++;
                }
            }
        }

        return answer;
    }

    private static int[][] makeSumArr(int[][] skill, int N, int M) {
        int[][] result = new int[N + 1][M + 1];

        for(int i = 0; i < skill.length; i++) {
            int type = skill[i][0];
            int degree = skill[i][5];
            if(type == 1) {
                degree *= -1;
            }

            result[skill[i][1]][skill[i][2]] += degree;
            result[skill[i][1]][skill[i][4] + 1] -= degree;
            result[skill[i][3] + 1][skill[i][2]] -= degree;
            result[skill[i][3] + 1][skill[i][4] + 1] += degree;
        }

        for(int i = 0; i < N + 1; i++) {
            for(int j = 1; j < M + 1; j++) {
                result[i][j] += result[i][j - 1];
            }
        }

        for(int j = 0; j < M + 1; j++) {
            for(int i = 1; i < N + 1; i++) {
                result[i][j] += result[i - 1][j];
            }
        }

        return result;
    }
}