[알고리즘] 2022 KAKAO BLIND 파괴되지 않은 건물 (Java)

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

프로그래머스

 

문제 설명에서도 강조되어 있듯, 효율성을 강조하는 문제이다. 

 

구간별로 공격 또는 회복하여 건물의 내구도 값의 변화가 발생하고,

 

이러한 형태의 문제는 아마 백준 문제를 많이 풀었다면 자주 봤을 누적합 형태의 문제였기 때문에 누적합을 활용하여 문제를 풀었다.

 

공격 또는 회복이 반복되는 회수는 skill 배열의 길이와 같기 때문에,

 

해당 길이만큼 반복문을 돌면서 각각의 skill에 맞는 값들을 합산해뒀다가 한 번에 계산하는 식으로 구현했다.

 

구간에 연산할 값을 배열에 다 저장하여 나중에 한 번에 연산할 배열을 선언하는 방식으로 구현했는데,

 

예를 들어 (0,0)부터 (N,N) 구간까지 회복을 해야하는 경우, (0,0)과 (N,N) 위치에는 +에 해당하는 값(degree)를,

 

(0,N+1)과 (N+1,0) 위치에는 -에 해당하는 값(degree)를 저장할 경우

 

나중에 누적합 연산을 실행할 경우 (0,0)부터 (N,N) 구간까지 +값(회복)이 반영되게 된다.

 

 

class Solution {
    static int r,c;
    static int attack[][];
    static int total[][];
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int val;
        
        r = board.length;
        c = board[0].length;
        
        attack = new int[r+1][c+1];
        
        for(int input[]:skill){
            val = input[5];
            if(input[0]==1){
                val = (-1)*val;
            }
            attack[input[1]][input[2]] += val;
            attack[input[1]][input[4] + 1] -= val;
            attack[input[3] + 1][input[2]] -= val;
            attack[input[3] + 1][input[4] + 1] += val;
        }
        
        total = new int[r+1][c+1];
        
        for(int i=0; i<r; i++) {
            total[i][0] = attack[i][0];
            for(int j=1; j<c; j++) {
                total[i][j] = attack[i][j] + total[i][j - 1];
            }
        }
        // 세로로
        for(int j=0; j<=c; j++) {
            for(int i=1; i<=r; i++){
                total[i][j] += total[i-1][j];
            }
        }
        
        for(int i=0; i<r; i++) {
            for (int j=0; j<c; j++) {
                if(board[i][j] + total[i][j] > 0) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
}