파괴되지 않은 건물

• 링크

코딩테스트 연습 - 파괴되지 않은 건물 | 프로그래머스 스쿨

• 푼 방법

이 문제의 핵심은 시간복잡도를 줄임에 있다.

1. skill 이 발동될 때, 범위에 있는 건물 모두에 데미지를 주는 방법은 당연히 안된다.
2. 그렇게 되면 시간 복잡도는 최대 skill.length * H * W 가 되버린다.
3. 그렇다면 여기서 skill 이 발동될 때마다 간편하게 기록하고, 나중에 다시 이를 활용하는 방법이 있다.
4. 일단 왼쪽에서 오른쪽으로 모든 행을 돌며 데미지를 줄 수 있는데, 이 때 미리 공격이 시작되는 셀, 그리고 공격이 끝나는 셀등을 기록해둘 수 있다.
5. 이를 기록하여 누적합을 이용하여 데미지를 순차적으로 셀에다가 쌓아가는 것이다.
6. 이를 기록하기 위해 skill 이 발동될 때마다, 범위의 모든 행에다가 기록을 하게 되면 최대 skill.length * H 가 된다.
7. 그렇기 때문에 이도 누적합을 이용해 순차적으로 셀에다가 데미지를 쌓아갔듯, 위에서 아래로 공격이 시작되는 셀, 공격이 끝나는 셀등을 기록해, 이를 누적합으로 계산 해줄 수 있는 것이다.
8. 즉 이 문제는 누적합의 누적합으로 풀어야하는 문제인 것이다.
9. 꽤나 어려운 문제였다 덜덜

• 시간 복잡도

O(skill.length + H * W);

• Code

class Solution {
    
    public int H;
    public int W;
    public int[][] b;
    public int[][] sum;
    
    public void execute(int r1, int c1, int r2, int c2, int damage) {
        sum[r1][c1] += damage;
        sum[r2 + 1][c1] -= damage;
        sum[r1][c2 + 1] -= damage;
        sum[r2 + 1][c2 + 1] += damage;
    }
    
    public void print() {
        for (int i = 0; i < H + 1; i++) {
            for (int j = 0; j < W + 1; j++) {
                System.out.print(sum[i][j] + " ");
            }
            System.out.println();
        }
        
        System.out.println("===========");
    }
    
    public int solution(int[][] board, int[][] skill) {
        this.H = board.length;
        this.W = board[0].length;
        this.b = board;
        this.sum = new int[H + 1][W + 1];
        
        for (int i = 0; i < skill.length; i++) {
            int type = skill[i][0] == 1 ? -1 : 1;
            execute(skill[i][1], skill[i][2], skill[i][3], skill[i][4], type * skill[i][5]);
            // print();
        }
        
        int add = 0;
        
        for (int i = 0; i < W + 1; i++) {
            int value = 0;
            for (int j = 0; j < H + 1; j++) {
                value += sum[j][i];
                sum[j][i] = value;
            }
        }
        
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W + 1; j++) {
                add += sum[i][j];
                
                if (j != W) {
                    b[i][j] += add;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (0 < b[i][j]) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
}