문제

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

풀이

처음에 문제 자체를 이해하는 것은 어렵지 않았다.

직사각형 범위와 그 구역에 1 ~ 100까지 +, -를 할 수 있고 마지막에 +인 구역의 수를 세주면 된다.

그림으로 예를 들면 전체가 1인 상태에서 (2, 0) 부터 (2, 3)까지 구역에 대해 -2만큼 공격을 한 상태이다.

이렇게 몇 차례 공격, 회복을 할 수 있고 마지막에 1 이상인 구역의 수를 세주는 문제이다.

문제는 시간복잡도(효율성)이다.

(N * M * skill행의 길이)를 하면 시간초과가 나게된다.

따라서 반복문을 일일이 돌면 안되고 효율적인 방법을 생각해야 한다.

1시간을 풀다가 방법을 생각해내지 못하여 풀이를 봤고 해답은 누적합이었다.

3 x 3의 board가 있고 (1, 1) ~ (2, 2)까지 -4를 한다고 해보자

처음에 이 상태일 것이다.

그리고 (1, 1) ~ (2, 2)까지 적용한 board의 값은 다음 그림과 같다.

이렇게 반복문을 돌며 계산해줘도 되지만 다음과 배열을 누적합으로 바꿔주는 과정으로 시간복잡도를 줄일 수 있다.

(1, 1), (2 + 1, 2 + 1)에 -4를 기록해주고
(1, 2 + 1), (2 + 1, 1)에 4를 기록해둔다.

그리고 왼쪽에서 오른쪽으로 누적합을 구해준다.

마찬가지로 위에서 아래로 누적합을 구해주면 처음에 구하려는 (1, 1) ~ (2, 2)까지 -4를 한 결과와 같다.

이중 for문으로 반복하며 구하지 않고 직사각형의 모서리에 표시만 해두고 마지막에 왼 -> 오, 위 -> 아래로 누적합을 구하는 방식이다.

---

마지막으로 주의해야 할 점은 새로운 board에 누적합 계산을 구하기 위해 표시를 해줘야 한다는 것이다.

처음 주어진 board의 상태는 누적합을 하고 나온 도화지라고 생각하면 편하다.

따라서 다른 표시 값과 누적합을 하게되면 다른 결과값이 나오기 때문에 0으로 초기화된 새로운 board에 누적합 표시를 해줘야 한다.

효율성 정답률이 1.8%인 것 만큼 처음에 2차원 누적합이라는 풀이를 생각하기 까다로웠던 것 같다.

범위가 주어지고 반복해서 구간을 채워가는 문제에서 효율성을 따질 때 누적합이 생각나게 하는 문제였다.

코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        
        int N = board.length;
        int M = board[0].length;
        
        int[][] storageBoard = new int[N + 1][M + 1];
        
        for(int i = 0 ; i < skill.length; 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 degree = skill[i][5];
            
          
            if(type == 1){
                storageBoard[r1][c1] -= degree;
                storageBoard[r2 + 1][c2 + 1] -= degree;
                storageBoard[r1][c2 + 1] += degree;
                storageBoard[r2 + 1][c1] += degree;
            }    
            else{
                storageBoard[r1][c1] += degree;
                storageBoard[r2 + 1][c2 + 1] += degree;
                storageBoard[r1][c2 + 1] -= degree;
                storageBoard[r2 + 1][c1] -= degree;
            }
            
        }
        
        for(int i = 0; i< N + 1;i++){
            for(int j = 1;j < M + 1;j++){
                storageBoard[i][j] += storageBoard[i][j - 1];
            }
        }
        
        for(int i = 1; i < N + 1;i++){
            for(int j = 0;j < M + 1;j++){
                storageBoard[i][j] += storageBoard[i - 1][j];
            }
        }
            
        for(int i = 0; i< N ;i++){
            for(int j = 0; j< M;j++){
                board[i][j] += storageBoard[i][j];
            }
        }
        
        for(int i = 0; i< N;i++){
            for(int j = 0 ;j<M;j++){
                if(board[i][j] > 0){
                    answer++;
                }
            }
        }
        
        return answer;
    }
}