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

문제

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

프로그래머스

 

문제 분석

건물의 내구도가 담겨있는 board 가 주어지고 skill 을 통해 건물의 내구도를 깍거나 회복할 수 있다.

skill 을 적용한 결과 파괴되지 않은 건물의 수를 반환하는 문제이다.

 

board 의 크기는 최대 1000 X 1000 이고 skill 은 최대 100개 이다.

 

skill 의 적용 범위가 항상 최대치라고 가정하고 그 결과를 board 에 계속 반영한다고 한다면

100 X 1000 X 1000 번 계산해야 하기 때문에 시간 초과가 날 것이다...

 

 

문제 접근

이 문제는 부분합을 이용해야 한다.

https://www.youtube.com/watch?v=HQD39nehBLQ&t=1398s

 

위의 일차원 배열을 변경 범위 마다 배열을 순회하며 직접 값을 변경해주면 4개의 배열의 크기만큼 모두 순회해야 하기 때문에 시간이 많이 걸린다.

 

위의 그림에서 파란 부분만 생각해보자.

변경 시작 지점에 +2 그리고 변경 끝의 다음 지점에 -2 를 넣는다.

그럼 앞에서 부터 부분합을 계산하면 아래와 같이 나온다.

 

0 0 2 2 2 2 2 2 2 0 0 0

 

이를 이차원 배열에 적용하면 된다.

https://www.youtube.com/watch?v=HQD39nehBLQ&t=1398s

 

코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int result = 0;
        int[][] actBoard = new int[board.length+1][board[0].length+1];

        for (int[] skillInfo : skill) {
            int type = skillInfo[0];
            int r1 = skillInfo[1], c1 = skillInfo[2];
            int r2 = skillInfo[3], c2 = skillInfo[4];
            int degree = skillInfo[5];

            if(type==1) degree *= -1;

            actBoard[r1][c1] += degree;
            actBoard[r2 + 1][c2 + 1] += degree;
            actBoard[r2 + 1][c1] += -degree;
            actBoard[r1][c2 + 1] += -degree;
        }

        // 행 방향으로 누적합
        for (int r = 1; r < actBoard.length - 1; r++) {
            for (int c = 0; c < actBoard[0].length - 1; c++) {
                actBoard[r][c] += actBoard[r - 1][c];
            }
        }

        // 열 방향으로 누적합
        for (int r = 0; r < actBoard.length - 1; r++) {
            for (int c = 1; c < actBoard[0].length - 1; c++) {
                actBoard[r][c] += actBoard[r][c - 1];
            }
        }

        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (board[r][c] + actBoard[r][c] > 0) {
                    result++;
                }
            }
        }
        return result;
    }
}

 

 

참고 자료

https://www.youtube.com/watch?v=HQD39nehBLQ&t=1398s