[2022 카카오 블라인드]파괴되지 않은 건물★

📍 문제 설명

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

프로그래머스

 

💡 접근

풀면서 느꼈지만 당연하게 효율성에서 걸렸던 문제다.

O(N*M)을 O(1)로 바꾸기 위해서 누적합 개념을 이용해야 했는데 2차원 배열로 확장된 케이스라 어느정도 고려할 부분이 있었지만 1차원 배열에서의 누적합 개념을 제대로 이해하고 있었으면 풀 수 있을 문제였을 것 같다.

누적합 유형도 간혹가다가 출제되는 것 같으니 어느정도 익혀놓는 것이 좋을 것 같다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;

        int[][] prefixSum = new int[board.length+1][board[0].length+1];
        for(int i = 0; i < skill.length; i++) {
            int kind = skill[i][0];
            int startX = skill[i][1]; // 0
            int startY = skill[i][2]; // 0
            int endX = skill[i][3]; // 3
            int endY = skill[i][4]; // 4
            int dur = skill[i][5] * (kind == 1 ? -1 : 1);

            // (0, 0) 부터 (3, 4) 까지 내구도 변화
            // 여기서 한번에 더할수 있는거 찾아봐야겠는데.. -> 2차원 배열 누적합
            prefixSum[startX][startY] += dur;
            prefixSum[endX+1][startY] -= dur;
            prefixSum[startX][endY+1] -= dur;
            prefixSum[endX+1][endY+1] += dur;
        }

        for(int i = 0; i < prefixSum.length; i++){
            int sum = 0;
            for(int j = 0; j < prefixSum[i].length; j++){
                sum += prefixSum[i][j];
                prefixSum[i][j] = sum;
            }
        }
        for(int i = 0; i < prefixSum.length; i++){
            int sum = 0;
            for(int j = 0; j< prefixSum.length; j++){
                sum += prefixSum[j][i];
                prefixSum[j][i] = sum;
            }
        }

        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                if(board[i][j] + prefixSum[i][j] > 0) answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        int[][] board = {{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,5},{5,5,5,5,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}};
        main.solution(board, skill);
    }
}