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

문제 설명

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

문제 풀이

• 구간합을 이용하여 풀이하였다.
• 우선 일반적으로 풀이한다면 시간 복잡도는 O(가로x세로x스킬갯수)가 되므로 시간초과가 발생한다.
• 결국 스킬을 사용하며 보드를 수정할때 전체 수정을 하면 안된다.
• 이를 위해 구간합을 사용했는데 설명은 다음과 같다.

  (0, 0) , (1, 1) 구간에 3을 더한다고 가정한다.

  • (r1, c1)에 3을 더함
  • (r1, c2+1)에 -3을 더함
  • (r2+1, c1)에 -3을 더함
  • (r2+1, c2+1)에 3을 더함

  이때 보드의 상태는 아래와 같다 (O(1) 걸리는 작업)
  -[3,0,-3]
  -[0,0,0]
  -[-3,0,3]

  추후 변경된 보드로 복원하는 과정은 각 행과 열에 대해 구간합을 구해주면 된다.

  행 기준 구간합을 구하면 다음과 같다.
  -[3,3,0]
  -[0,0,0]
  -[-3,-3,0]
  열 기준 구간합을 구하면 다음과 같다.
  -[3,3,0]
  -[3,3,0]
  -[0,0,0]

  위 배열은 초기 원했던 보드의 상태와 같아진다.

소스 코드 (JAVA)

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int N = board.length;     //행 길이
        int M = board[0].length;  //열 길이
        int S = skill.length;     //skill 개수 
        //초기화
        int[][] preSum = new int[N+1][M+1];
        for (int i = 0; i < S; i++) {
            int type = skill[i][0];
            int r1 = skill[i][1];
            int c1 = skill[i][2];
            int r2 = skill[i][3];
            int c2 = skill[i][4];
            int d = skill[i][5];
            preSum[r1][c1] += (type == 1 ? -d : d);
            preSum[r1][c2 + 1] += (type == 1 ? d : -d);
            preSum[r2 + 1][c1] += (type == 1 ? d : -d);
            preSum[r2 + 1][c2 + 1] += (type == 1 ? -d : d);
        }
        //누적합 계산 (스킬 사용 이후 보드 복원)
        //행 누적합 
        for (int i = 0; i < N + 1; i++) {
            int sum = 0;
            for (int j = 0; j < M + 1; j++) {
                sum += preSum[i][j];
                preSum[i][j] = sum;
            }
        } 
        //열 누적합 
        for (int j = 0; j < M + 1; j++) {
            int sum = 0;
            for (int i = 0; i < N + 1; i++) {
                sum += preSum[i][j];
                preSum[i][j] = sum;
            }
        }
        //기존 배열에 더하면서 파괴되지 않은 건물 카운트 
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] + preSum[i][j] > 0)
                    res++;
            }
        }
        return res;
    }
}