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

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

프로그래머스

 

접근 방법

1. 문제를 읽으며, 일반 적인 브루트포스 기반의 구현을 생각했지만, 데이터의 크기 상 불가능했다.
2. 다른 방법을 시도했으나 시간 초과였고, 결국 해설을 읽고 문제를 풀었다. 해설에서는 누적합을 기반으로 문제를 해결했다.
3. skill 배열을 순회하며 board에 적용할 마스크를 만들고 마지막에 더해주는 방법이다.
4. 1차원 배열에서 마스크를 만드는 방법
   1. [1,3,5,23,5,9]의 배열에서 1 ~ 3번 원소에 -4, 0 ~ 5번 원소에 +2를 한다고 가정하겠다. (즉, [3,1,3,21,7,11]을 만들어야한다)
   2. [0,0,0,0,0,0,0] 으로 기존 배열보다 큰 사이즈의 배열을 만든다
   3. 기존 배열에 더하는 범위 시작지점과 같은 곳에 원하는 값을 저장하고, 범위 마지막 지점 +1에 반대 부호로 저장한다. 이를 수행하면 다음과 같다.
   4. [0,-4,0,0,4,0,0] -> [2,-4,0,0,4,0,-2] 
   5. 이후 이를 누적합( [2,-2,-2,-2,2,2,0] ) 하여 기존 배열에 원소별로 더해주면 답이 된다.
5. 이를 응용하여 2차원 배열에서 다음과 같이 마스크를 만들 수 있다.

[0,0,0,0]

[0,0,0,0]

[0,0,0,0]

[0,0,0,0]

 

(기존 크기가 3*3배열에서 (1,1), (2,2)의 범위에 -4를 해야한다)

 

[0,0,0,0]          [0,0,0,0]          [0,0,0,0]

[0,-4,0,4]    >   [0,-4,0,4]    >   [0,-4,-4,0]

[0,0,0,0]     >   [0,-4,0,4]     >  [0,-4,-4,0]

[0,4,0,-4]         [0,0,0,0]          [0,0,0,0]

 

위 처럼 상하, 좌우 로 누적합을 수행하면 마스크를 만들 수 있다. 1차원 마스크를 만들때 처럼, 수행(skill)이 많다면 4개의 점만 찍어놓고 누적하면 마스크를 만들 수 있다.

코드

import java.util.*;
class Solution {
    int n ,m;
    public int solution(int[][] board, int[][] skill) {
        n = board.length;
        m = board[0].length;
        int[][] newBoard = getNewBoard(skill); 
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                board[i][j] += newBoard[i][j];
            }
        }
        
        return getAns(board);
    }
    int[][] getNewBoard(int[][] skill){
        int[][] newBoard = new int[n+1][m+1];
        
        for(int[] s: skill){
            int r1 = s[1], c1 = s[2];
            int r2 = s[3], c2 = s[4];
            int v = s[0] == 1 ? -s[5] :s[5];
            
            newBoard[r1][c1] += v;
            newBoard[r1][c2+1] += -v;
            newBoard[r2+1][c1] += -v;
            newBoard[r2+1][c2+1] += v;
        }
        
        // 좌 -> 우
        for(int i = 0 ; i < n ; i++){
            for(int j = 1 ; j < m ; j++){
                newBoard[i][j] += newBoard[i][j-1];
            }
        }
        
        //상 -> 하
        for(int i = 0 ; i < m ; i++){
            for(int j = 1 ; j < n ; j++){
                newBoard[j][i] += newBoard[j-1][i];
            }
        }
        
        return newBoard;
    }
    int getAns(int[][] board){
        int cnt = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                if(board[i][j] > 0) cnt++;
            }
        }
        return cnt;
    }
}