이번에 풀어본 문제는
프로그래머스 파괴되지 않은 건물 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int n = board.length;
        int m = board[0].length;
        int [][] prefix_arr = new int[n+1][m+1];
        
        for(int [] row : skill)
        {
            int type = row[0];
            int degree = type == 1 ? -row[5] : row[5];
            int r1 = row[1];
            int c1 = row[2];
            int r2 = row[3];
            int c2 = row[4];
            
            for(int i = r1; i <= r2; ++i)
            {
                prefix_arr[i][c1] += degree;
                prefix_arr[i][c2+1] += -degree;
            }
        }
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                if(j != 0) prefix_arr[i][j] += prefix_arr[i][j-1];
                board[i][j] += prefix_arr[i][j];
                if(board[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
}

📝 풀이

공격 / 회복 두가지 타입의 입력을 받아, 공격일경우 주어진 입력범위만큼 건물의 내구도를 감소시키며, 회복은 내구도를 회복시키는 과정을 진행합니다.
입력 개수만큼 위 과정을 진행한 후, 남아있는 건물 중 내구도가 0 이상인, 즉 파괴되지 않은 건물의 개수를 리턴해주는 문제입니다.
말 그대로 배열에 담아 입력 순서대로 증감시켜주면 쉽게 풀 수 있는 문제지만, 해당 문제는 효율성을 체크하는 문제이기 때문에 누적합을 활용해주어야 합니다. 누적합의 활용법은 1차원 배열과 크게 다르지 않으며, 변경이 시작되는 인덱스에 degree값을 더해주고, 끝나는 인덱스+1 자리에는 degree값을 빼준 후, 최종적으로 남은 prefix_arr값들을 인덱스 순서대로 누적합 해주면 해당 위치에 누적된 증감결과가 남게 됩니다. 마지막으로 초기 상태의 배열인 board배열과 prefix_arr배열의 각 인덱스를 서로 더해주면 결과 내구도를 얻을 수 있습니다.

📜 후기

2022 카카오 블라인드 코딩테스트 6번 문제입니다.
코딩테스트를 봤을 당시에 누적합을 몰랐어서, 효율성을 통과하지 못했었습니다. 문제가 공개되면 꼭 다시 풀어보고 싶어서 메모해뒀었는데, 마침 며칠전에 올라와서 다시 풀어보게 되었습니다. 알고 푸니까 엄청 간단한 문제였는데, 부족함을 다시한번 느끼게됐네요...ㅠㅠ