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

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

프로그래머스

 

---

 

문제 개요

이 문제는 N x M 크기의 게임 맵에서 건물들의 내구도를 관리하는 문제다. 각각의 칸에 건물이 존재하며, 적군은 직사각형 범위로 건물의 내구도를 감소시키는 공격을, 아군은 직사각형 범위로 내구도를 증가시키는 회복 스킬을 사용한다. 모든 공격과 회복이 끝난 후, 내구도가 1 이상인 건물의 개수를 계산하는 것이 목표다.

 

 

접근 방법

이 문제는 누적합을 활용한 2차원 차이 배열 (2D Difference Array) 기법으로 해결해야 효율성 테스트를 통과할 수 있다. 단순하게 매번 범위 내의 모든 셀을 직접 갱신하면 시간 복잡도가 O(K * N * M)까지 올라가 비효율적이므로, 스킬의 효과만 기록하고, 최종적으로 한 번에 누적합을 계산해 적용하는 방식이 필요하다.

1. 스킬 효과 누적 기록

• arr이라는 board보다 한 행, 한 열씩 큰 보조 배열을 생성
• 각 스킬에 대해 2차원 차이 배열 방식으로 영향을 기록
  • 공격이면 -degree, 회복이면 +degree를 해당 사각형 네 꼭짓점에 적절히 더하거나 빼서 누적 효과를 기록

2. 가로 누적합 적용

• 각 행에 대해 왼쪽에서 오른쪽으로 누적합을 구해 실제 영향을 계산

3. 세로 누적합 적용

• 각 열에 대해 위쪽에서 아래쪽으로 누적합을 구해 최종 영향을 반영

4. board에 영향 반영 및 파괴되지 않은 건물 계산

• 위에서 계산된 누적 내구도 변경값을 board의 각 위치에 더하고, 최종 내구도가 1 이상인 경우를 세어 반환

 

코드

import java.util.*;
class Solution {
    static int[][] arr;
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        init(board.length, board[0].length, skill);
        
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                board[i][j] += arr[i][j];
                if(board[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
    
    public void init(int r, int c, int[][] skill) {
        arr = new int[r+1][c+1];
        
        for(int[] a : skill) {
            int type = a[0];
            int r1 = a[1];
            int c1 = a[2];
            int r2 = a[3];
            int c2 = a[4];
            int degree = a[5];
            
            degree = type == 1 ? -degree : degree;
            
            arr[r1][c1] += degree;
            arr[r1][c2+1] -= degree;
            arr[r2+1][c1] -= degree;
            arr[r2+1][c2+1] += degree;
        }
        
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[0].length-1; j++) {
                arr[i][j+1] += arr[i][j];
            }
        }
        
        for(int i=0; i<arr[0].length; i++) {
            for(int j=0; j<arr.length-1; j++) {
                arr[j+1][i] += arr[j][i];
            }
        }
    }
}