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

문제 주소

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

풀이 과정

시행착오

이 문제는 효울성을 고려하지 않는다면 풀이 자체는 어렵지 않은 문제이다. 보드에 각 칸마다 주어진 조건에 따라 숫자를 더하거나 뺀 후, 마지막에 보드의 칸중 숫자가 0보다 큰것의 개수를 세면 된다.

다만 이렇게 코드를 작성하면 효율성 테스트에서 모두 시간초과가 발생하게 된다.

코드를 부분적으로 돌려보면서 어느 부분이 시간이 오래걸리는지를 확인해본 결과 스킬을 사용하는 부분(보드의 칸중 일부의 숫자가 증가하거나 감소)의 시간을 감소시켜야 한다는 것을 알게 되었다.
효율성 테스트의 경우 스킬 사용 횟수가 최대 250000회나 되기 때문에 기존 로직의 스킬 1회 사용의 시간복잡도가 O(n^2)인것을 감안하면 상당히 많은 시간이 걸린다.

결국 스킬을 사용할때마다의 연산횟수를 줄여야 한다. 이 문제의 경우 숫자가 변하는 칸의 형태가 반드시 직사각형이어야 한다는 조건덕분에 연산횟수를 줄이는 것이 가능했다.

상세 풀이

스킬 사용

board와 크기가 같은 inte라는 배열을 만들고, 만약 (0, 0)부터 (a, b)까지 k만큼 회복되면 inte의 (a, b)에 k가 추가되도록 했다.
위 규칙을 사용해서, (a, b)부터 (c, d)까지 k만큼 회복되는 경우도 표현할 수 있다.
일단, inte의 (c, d)에 k를 추가한다. 그다음에 (a, b)부터 (c, d)까지에 속하지 않는 부분을 제거해야 하므로 (a - 1, d), (c, b - 1)에 -k를 추가한다. 마지막으로 (a - 1, b - 1)에 k를 추가하여 중복으로 감소된 부분을 보정한다.

위 방법을 사용하면 스킬을 한번 사용할때 필요한 시간이 상수시간(최대 4회)가 되어 시간을 크게 단축할 수 있다.

파괴되지 않은 건물 계산

스킬을 모두 사용하고 나면, inte 배열을 복원해서 board와 비교해야 한다. 최종적으로 각 칸에 숫자가 어떻게 변화했는지는 다음과 같다.
먼저 (0, 0)에는 inte의 모든 칸의 총합만큼이 더해진다. (0, 1)에는 배열의 2번째 요소의 값이 1 이상인 모든칸의 총합만큼이 더해진다. 이를 일반화하면
(a, b)에는 $\int_a^{x_{max}}\int_b^{y_{max}}(inte)dxdy$ = 배열의 요소가 각각 a, b 이상인 모든 칸의 총합 만큼이 더해진다. 이 값을 기존의 board에 더했을 때 0보다 크면 카운트를 하면 된다.

실제 총합 계산은 2단계로 나누어진다
1. 각 열마다 아래에서부터 위로 합산 - 각 열마다 맨 아래에서부터, 현재칸과 바로 아래칸을 더한다.
2. 각 행마다 오른쪽에서부터 왼쪽으로 합산 - 각 행마다 맨 오른쪽에서부터, 현재칸과 바로 오른쪽 칸을 더한다.

적분 계산에서도 x에 대한 적분과 y에 대한 적분을 각각 계산할 수 있기 때문에, 위와 같은 계산이 가능하다.

최종 코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        Board result = new Board(board);
        Arrays.stream(skill).forEach(s -> {
            int type = s[0];
            switch(type){
                case 1:
                    result.attack(s[1], s[2], s[3], s[4], s[5]);
                    break;
                case 2:
                    result.heal(s[1], s[2], s[3], s[4], s[5]);
                    break;
                default:
                    break;
            }
        });
        return result.getSavedBuilding();
    }
    private class Board{
        int[][] board;
        int[][] inte;
        public Board(int[][] board){
            this.board = board;
            this.inte = new int[board.length][board[0].length];
        }
        
        public void attack(int r1, int c1, int r2, int c2, int degree){
            action(r1, c1, r2, c2, -degree);
        }
        public void heal(int r1, int c1, int r2, int c2, int degree){
            action(r1, c1, r2, c2, degree);
        }
        
        private void action(int r1, int c1, int r2, int c2, int degree){
            inte[r2][c2] += degree;
            if(r1 > 0) inte[r1 - 1][c2] -= degree;
            if(c1 > 0) inte[r2][c1 - 1] -= degree;
            if(r1 > 0 && c1 > 0) inte[r1 - 1][c1 - 1] += degree;
        }
        public int getSavedBuilding(){
            int count = 0;
            for(int j = 0; j < inte[0].length; j++){
                for(int i = inte.length - 1; i > 0; i--){
                    inte[i - 1][j] += inte[i][j];
                }
            }
            for(int i = 0; i < inte.length; i++){
                for(int j = inte[0].length - 1; j > 0; j--){
                    if(inte[i][j] > -board[i][j]) count++;
                    inte[i][j - 1] += inte[i][j];
                }
            }
            for(int i = 0; i < inte.length; i++){
                if(inte[i][0] > -board[i][0]) count++;
            }
            return count;
        }
    }
}