문제

Programmers Lv3, 파괴되지 않은 건물

핵심

• 입력의 크기가 1,000과 250,000이라 대략 $O(N^2)$이하 알고리즘을 사용한다.
• 스킬에 따라 벽 내구도를 낮추고, 높인다. 마지막에 벽 내구도가 0을 초과하여 부서지지 않은 개수를 반환하면 된다. 최대 $1000 * 1000$ 크기의 행렬이고, 스킬 횟수는 최대 $250,000$까지 가능해서 3중 루프를 이용해서 풀면 당연히 시간초과가 난다.
• 누적 합을 이용하면 벽 내구도를 조작하는 과정을 단순화시켜 $O(N^2)$풀이가 가능하다. 범위에 속하는 모든 값을 변경하는 게 아닌 경계만 검사한다. 예를 들어 (0, 0)에서 (2, 2)의 내구도를 4만큼 깎는다면 아래와 같이 표현할 수 있다.

• 하지만 해당 방식으로는 시간 복잡도를 $O(N^2)$으로 줄일 수 없다. 하지만, 누적합을 이용하면서 각 경계만(4개) 체크해주면 이는 상수시간에 동작하게 된다. 아이디어를 살펴보자. 위의 그림은 아래처럼 나타낼 수도 있다.

• 행과 열 각각에 누적합을 계산하면 아래와 같이 숫자가 채워진다. 먼저 행을 계산하고, 그다음 열을 계산한다.

• 위 아이디어를 코드로 작성하면 아래와 같이 표현할 수 있다.

void do_skill(int type, int r1, int c1, int r2, int c2, int degree) {
    
    degree = type == 1 ? degree * -1 : degree;
    
    cumSum[r1][c1] += degree; // 시작점
    cumSum[r1][c2 + 1] -= degree; // 행
    cumSum[r2 + 1][c1] -= degree; // 열
    cumSum[r2 + 1][c2 + 1] += degree; // 연속(행열) 차감 복구
}

• 모든 스킬을 순회하면서 이를 상수 시간에 처리한 후 처음 벽 내구도 상태에 반영하여 부서지지 않은 벽의 개수를 구하면 된다.

개선

코드

C++

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cumSum[1004][1004];

void do_skill(int type, int r1, int c1, int r2, int c2, int degree) {
    
    degree = type == 1 ? degree * -1 : degree;
    
    cumSum[r1][c1] += degree; // 시작점
    cumSum[r1][c2 + 1] -= degree; // 행
    cumSum[r2 + 1][c1] -= degree; // 열
    cumSum[r2 + 1][c2 + 1] += degree; // 연속(행열) 차감 복구
}

int solution(vector<vector<int>> board, vector<vector<int>> skill) {

    for (auto s : skill) {
        do_skill(s[0], s[1], s[2], s[3], s[4], s[5]);
    }

    for (int i = 0; i <= board.size(); ++i) {
        for (int j = 0; j < board[0].size(); ++j) {
            cumSum[i][j + 1] += cumSum[i][j];
        }
    }    
    
    for (int j = 0; j <= board[0].size(); ++j) {
        for (int i = 0; i < board.size(); ++i) {
            cumSum[i + 1][j] += cumSum[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[0].size(); ++j) {
            if (board[i][j] + cumSum[i][j] > 0) ++ans;
        }
    }

    return ans;
}

Java

class Solution {
    int[][] cumSum;

    void doSkill(int type, int r1, int c1, int r2, int c2, int degree) {
        degree = type == 1 ? degree * -1 : degree;

        cumSum[r1][c1] += degree; // 시작점
        cumSum[r1][c2 + 1] -= degree; // 행
        cumSum[r2 + 1][c1] -= degree; // 열
        cumSum[r2 + 1][c2 + 1] += degree; // 연속(행열) 차감 복구
    }

    public int solution(int[][] board, int[][] skill) {
        int n = board.length;
        int m = board[0].length;
        cumSum = new int[n + 4][m + 4];

        for (var s : skill) {
            doSkill(s[0], s[1], s[2], s[3], s[4], s[5]);
        }

        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j < m; ++j) {
                cumSum[i][j + 1] += cumSum[i][j];
            }
        }

        for (int j = 0; j <= m; ++j) {
            for (int i = 0; i < n; ++i) {
                cumSum[i + 1][j] += cumSum[i][j];
            }
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (board[i][j] + cumSum[i][j] > 0) ++ans;
            }
        }

        return ans;
    }
}