[Lv.3] 파괴되지 않은 건물

정확성100, 효율성 0 코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;

        answer=board.length*board[0].length;
        for (int[] nowSkill : skill) {
            int type=nowSkill[0];
            int modi;
            if(type==1)
                modi=-1;
            else modi=1;
            int startX=nowSkill[1];
            int startY=nowSkill[2];
            int endX=nowSkill[3];
            int endY=nowSkill[4];
            int degree=nowSkill[5];
            for (int i = startX; i <=endX ; i++) {
                for (int j = startY; j <=endY ; j++) {
                    boolean flag=false;
                    if(board[i][j]>0)
                        flag=true;
                    board[i][j]+=degree*modi;
                    if(board[i][j]>0){
                        //해당 스킬 시행 후 벽이 존재하는 경우, 기존에 있던 벽이라면 벽 개수 변화X / 기존에 벽이 없었다면 벽 갯수 ++
                        if(!flag)
                            answer++;
                    }else{
                        //스킬 시행 후 벽 소멸, 기존의 벽 있었으면 벽 갯수 -- / 원래 없었으면 변화 X
                        if(flag)
                            answer--;
                    }
                }
            }
        }
        return answer;
    }
}

통과 코드(정확성 100, 효율성 100)

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int[][] skillBoard=new int[board.length+1][board[0].length+1];
        for (int[] nowSkill : skill) {
            int type=nowSkill[0];
            int modi;
            if(type==1)
                modi=-1;
            else modi=1;
            int startX=nowSkill[1];
            int startY=nowSkill[2];
            int endX=nowSkill[3];
            int endY=nowSkill[4];
            int degree=nowSkill[5];

            skillBoard[startX][startY]+=degree*modi;
            skillBoard[endX+1][startY]-=degree*modi;
            skillBoard[startX][endY+1]-=degree*modi;
            skillBoard[endX+1][endY+1]+=degree*modi;
        }

        for (int i = 1; i < board[0].length; i++) {
            for (int j = 0; j <board.length; j++) {
                skillBoard[j][i]+=skillBoard[j][i-1];
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j <board[0].length; j++) {
                if(i==0){
                    if(skillBoard[i][j]+board[i][j]>0)
                        answer++;
                }else{
                    skillBoard[i][j]+=skillBoard[i-1][j];
                    if(skillBoard[i][j]+board[i][j]>0)
                        answer++;
                }

            }
        }

        return answer;
    }
}

---

처음엔 왜이렇게 쉬운 문제가 나왔지? 싶었는데, 역시 쉬운 문제가 아니였다..

단순히 정답을 산출하는 건 쉬운 문제지만, 이 문제를 효율적으로 풀기 위해선 2차원 누적합을 사용해야 한다.

누적합이란 Si=Si-1+Ai를 이용해서 푸는 방식인데

내가 0번 인덱스부터 2번 인덱스까지 2를 추가하고 싶다면 loop를 돌면서 각 값에 +2를 해주는 것이 아니라,

누적합 배열을 만들어 0번 인덱스에 2 3번인덱스에 -2를 더해준다.

그렇게 되면 누적합 개념을 사용해서 나중에 필요한 상황에서, 결과값[1] = 누적합[0]+배열[1] 이런식으로 간편하게 사용할 수 있게 되는 것이다.

이는, 2차원으로 확장해도 같은데 1,1 부터 2,2까지 2를 더하고 싶다면 누적합[1,1]에 2를 더하고 누적합[2+1,1], [1,2+1]에 2를 빼고 누적합[2+1,2+1]엔 2를 다시 더해주고 오른쪽으로 누적합을 한번 쭉 돌리고 (모든 행) , 아래로 누적합을 쭉 돌리면 (모든 열) 결과배열을 구할 수 있게 된다.

주의할 점은, 여기선 스킬이 최대25만개이기에 각 스킬이 적용되는 직사각형의 넓이를 N이라 했을 떄 스킬 배열의 크기*N번의 반복이 발생하게 된다. 이 값과 배열을 선회하는 비용을 비교했을 때 스킬이 충분히 이득이 된다고 판단되면 누적합을 적용해야 한다.

여기선 배열의 최대 크기는 100만이고 스킬이 25만개*N인데, 여기서 N은 충분히 클 수 있기 때문에 배열을 선회하는 비용보다 스킬마다 반복을 하는 행위가 훨씬 큰 부담이 되기에 누적합을 사용해야 한다.