[Java] 프로그래머스 [Level-4] [3차]파괴되지 않은 건물

public class Solution {
	
	// 파괴되지 않은 건물
	
	public static int solution(int[][] board, int[][] skill) {
		int answer = 0;
		int[] arr = new int[skill[0].length];
		int startRowNum = 0;
		int startColNum = 0;
		int endRowNum = 0;
		int endColNum = 0;
		int affectPoint = 0;
        
		for (int i = 0; i < skill.length; i++) {
			arr = skill[i];
        	
			startRowNum = arr[1];
			startColNum = arr[2];
			endRowNum = arr[3];
			endColNum = arr[4];
        	
			affectPoint = (arr[0] == 1 ? -arr[5] : arr[5]);
        	
			for (int j = startRowNum; j <= endRowNum; j++) {
        		
				for (int z = startColNum; z <= endColNum; z++) {
					board[j][z] += affectPoint;
				}
			}
		}
        
		for (int j = 0; j < board.length; j++) {
    		
			for (int z = 0; z < board[j].length; z++) {
//				System.out.print(board[j][z] + " ");
				if (board[j][z] > 0) answer++;
			}
//			System.out.println();
		}
		
	return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] board = {{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5}}; // 4개의 행 5개의 열
		int[][] skill = {{1,0,0,3,4,4},{1,2,0,2,3,2},{2,1,0,3,1,2},{1,0,1,3,3,1}}; // 1은 공격, 2는 회복 // {1,0,0,3,4,4}는 공격이며 0행0열 ~ 3행4열까지 4의 피해를 준다는 의미
		
		System.out.println(solution(board, skill)); // 10
	}
}

시간 초과 발생

 

<누적합 이용한 문제 풀이>

public class Solution {
	
	// 파괴되지 않은 건물
	
	public static int solution(int[][] board, int[][] skill) {
		int answer = 0;
		int N = board.length;
		int M = board[0].length;
		int[][] sumArr = new int[N+1][M+1];
		int[] infoArr = new int[skill[0].length];
		int startRowNum = 0;
		int startColNum = 0;
		int endRowNum = 0;
		int endColNum = 0;
		int affectPoint = 0;
        
		for (int i = 0; i < skill.length; i++) {
			infoArr = skill[i];
        	
			startRowNum = infoArr[1];
			startColNum = infoArr[2];
			endRowNum = infoArr[3];
			endColNum = infoArr[4];
        	
			affectPoint = (infoArr[0] == 1 ? -infoArr[5] : infoArr[5]);
        	
			sumArr[startRowNum][startColNum] += affectPoint; // 좌상 +
			sumArr[startRowNum][endColNum + 1] += -affectPoint; // 좌하 -
			sumArr[endRowNum + 1][startColNum] += -affectPoint; // 우상 -
			sumArr[endRowNum + 1][endColNum + 1] += affectPoint; // 우하 +
		}
        
        
		// 상하의 합
		for (int i = 1; i < N; i++) {
        	
			for (int j = 0; j < M; j++) {
				sumArr[i][j] += sumArr[i - 1][j];
			}
		}
        
		// 좌우의 합
		for (int j = 1; j < M; j++) {
        	
			for (int i = 0; i < N; i++) {
				sumArr[i][j] += sumArr[i][j - 1];
			}
		}
        
		for (int i = 0; i < N; i++) {
        	
			for (int j = 0; j < M; j++) {
        		
				if (board[i][j] + sumArr[i][j] > 0) {
					answer++;
				}
			}
		}
        
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] board = {{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5}}; // 4개의 행 5개의 열
		int[][] skill = {{1,0,0,3,4,4},{1,2,0,2,3,2},{2,1,0,3,1,2},{1,0,1,3,3,1}}; // 1은 공격, 2는 회복 // {1,0,0,3,4,4}는 공격이며 0행0열 ~ 3행4열까지 4의 피해를 준다는 의미
		
		System.out.println(solution(board, skill)); // 10
	}
}

 

1 ~ 11 그림을 보면서 이해해 보자

중간에 번호가 붙지 않은 예시는 이해를 돕기 위한 설명이니 신경쓰지 않아도 된다.

 

 

공격 & 4이므로 첫 번째 값은 -4 하단과 우측 값은 4 우측 하단 값은 -4로 설정한다.

 

상하 누적 합의 범위는 N행(여기서는 4행)까지이므로 파란색 부분은 대상에서 제외

 

좌우 누적 합의 범위는 M열(여기서는 5열)까지이므로 파란색 부분은 대상에서 제외

 

 

 

 

 

 

 

 

 

 

 

프로그래머스 파괴되지 않은 건물 문제 풀이 Java