[프로그래머스/Java] Lv.3 - 파괴되지 않은 건물

승래·2026년 3월 21일

프로그래머스 Lv.3 - 파괴되지 않은 건물

요구사항

board 위의 건물에 skill을 적용한 후 파괴되지 않은 건물의 수를 구하는 문제
type 1: 범위 내 건물에 degree만큼 데미지
type 2: 범위 내 건물에 degree만큼 회복

접근 방식

2D 누적합(Difference Array) 으로 풀었다.

단순 이중포문이 시간초과인 이유

O(n * m * skill 수) = O(1000 * 1000 * 250,000) = O(250,000,000,000)
→ 완전 시간초과!

2D 누적합 아이디어

매번 범위를 순회하는 대신 범위의 꼭짓점 4군데만 표시하고
마지막에 한 번에 누적합으로 전파한다.

1D 누적합 원리:

2~4 범위에 +3 적용하고 싶을 때
diff[2] += 3, diff[5] -= 3

누적합 후: 0 0 3 3 3 0 0
→ 범위를 벗어나면 자동으로 0으로 돌아옴

2D 누적합: (r1,c1)~(r2,c2) 범위에 +N 적용

diff[r1][c1]     += N
diff[r1][c2+1]   -= N
diff[r2+1][c1]   -= N
diff[r2+1][c2+1] += N  ← 두 번 빠진 모서리를 다시 더함 (포함-배제 원리)

누적합 전파 순서

1. 행 방향으로 누적합
2. 열 방향으로 누적합
→ 각 칸에 최종 변화량이 반영됨

코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        int[][] diff = new int[row+1][col+1];

        for (int[] s : skill) {
            int type = s[0], r1 = s[1], c1 = s[2], r2 = s[3], c2 = s[4], degree = s[5];

            if (type == 1) {
                diff[r1][c1] -= degree;
                diff[r1][c2+1] += degree;
                diff[r2+1][c1] += degree;
                diff[r2+1][c2+1] -= degree;
            } else {
                diff[r1][c1] += degree;
                diff[r1][c2+1] -= degree;
                diff[r2+1][c1] -= degree;
                diff[r2+1][c2+1] += degree;
            }
        }

        // 행 방향 누적합
        for (int i = 0; i <= row; i++)
            for (int j = 1; j <= col; j++)
                diff[i][j] += diff[i][j-1];

        // 열 방향 누적합
        for (int j = 0; j <= col; j++)
            for (int i = 1; i <= row; i++)
                diff[i][j] += diff[i-1][j];

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                board[i][j] += diff[i][j];
                if (board[i][j] > 0) answer++;
            }

        return answer;
    }
}