[누적 합] 파괴되지 않는 건물(프로그래머스, 자바)

 

문제 

본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다. 건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

 

 

입력

행렬 모양의 맵의 값 

type(회복, 파괴), r1, c1, r2, c2, degree

 

출력

내구도가 0 초과인 파괴되지 않은 건물의 개수 

 

 

구현 

그냥 구현했을 때에는 효율성에서 문제 발생 => 누적합을 이용해서 시간 복잡도를 줄인다. 

 

1. 누적합의 원리 사용

class Solution {
	
    public int solution(int[][] board, int[][] skill) {
        
        int h=board.length;
        int w=board[0].length;
        int[][] map=new int[h+1][w+1];
        
        int answer = 0;
        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 power=skill[i][5];
             
          if(type==1) power*=-1;
          map[r1][c1]+=power;
          map[r1][c2+1]-=power;
          map[r2+1][c1]-=power;
          map[r2+1][c2+1]+=power;
         
          
        }
        
        //가로 누적합 
        for(int i=0;i<h;i++) {
            int sum=0;
        	for(int j=0;j<w;j++) {
        		sum+=map[i][j];
                map[i][j]=sum;
        	}
        }
        
        //세로 누적합
        for(int i=0;i<=w;i++){
            int sum2=0;
        	for(int j=0;j<=h;j++) {
                sum2+=map[j][i];
        		map[j][i]=sum2;
        	}
        }
        
        for(int i=0;i<h;i++) {
        	for(int j=0;j<w;j++) {
        		board[i][j]+=map[i][j];
        		if(board[i][j]>0) answer++;
        	}
        }
    				
        return answer;
    }
}