프로그래머스 - 파괴되지 않는 건물 Java

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

코딩테스트 연습 - 파괴되지 않은 건물

 

 

문제풀이 

효율성 테스트를 위해 누적합을 이용해 구현

시작점에 +N 끝점에 -N을 배치

상하 좌우 방향을 합산해 해당 구간의 최종 결과값을 구할 수 있다.

 

 

/*
skill type r1 c1 r2 c2 degree
type == 1 적의 공격
type == 2 회복 스킬

누적합을 이용해 시간 단축 
시작점에 +N 끝점에 -N
상하 방향 합산 + 좌우 방향 합산을 통해 구간의 값을 구할 수 있다. 

*/

import java.util.*;

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        
        int n = board.length;
        int m = board[0].length;
        
        int[][] sumBoard = new int[n+1][m+1];
        
        
        // 구간 지정
        for(int[] one : skill)
        {
            int type = one[0];
            int r1 = one[1];
            int c1 = one[2];
            int r2 = one[3];
            int c2 = one[4];
            int degree = one[5] * (type == 1 ? -1 : 1);
            
            sumBoard[r1][c1] += degree;
            sumBoard[r1][c2+1] -= degree;
            sumBoard[r2+1][c1] -= degree;
            sumBoard[r2+1][c2+1] += degree;
        }
        
        // 좌우 계산
        for(int i = 0; i < n; i++)
        {
            for(int j = 1; j < m; j++)
            {
                sumBoard[i][j] += sumBoard[i][j-1];
            }
        }
        
        // 상하 계산
        for(int j = 0; j < m; j++)
        {
            for(int i = 1; i < n; i++)
            {
                sumBoard[i][j] += sumBoard[i-1][j];
            }
        }
        
        // 건물 확인
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(board[i][j] + sumBoard[i][j] >= 1)
                {
                    answer++;
                }
            }
        }
        
        
        return answer;
    }
}