[Programmers] 파괴되지 않은 건물 - Java

📍 문제 📍

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

프로그래머스

 

 

📍 요약 📍

• 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 후, 파괴되지 않은 건물의 개수 구하기
• 적이 공격할 때는 내구도가 감소하고, 아군이 회복 스킬을 사용할 때는 내구도가 회복됨

 

📍문제 풀이 과정📍

• 공격과 회복이 반복되는데 모든 범위만큼 반복문을 일일이 실행하기엔 행, 열 각각 크기가 최대 1000이므로 시간 초과가 날 것 같았다. 그래서 모든 경우를 기록해두고 한꺼번에 실행하는 누적합을 생각했다.

 

📍풀이📍

1. 누적합을 기록할 배열 생성

2. 공격 혹은 회복 시작(=r1)에 degree 기록, 끝나는 부분 + 1 (=c2+1)에 부호를 반대로 한 -degree 기록

3. 모든 기록이 끝난 후, 누적합 계산

4. 누적합 계산과 건물의 내구도 값 계산하면서 내구도가 1이상이라면 answer++

 

 

📍시간 초과📍

처음에는 배열의 행에서만 누적합을 수행했는데 효율성 채점에서 0점이었다. 풀면서도 공격, 회복을 기록할 때 시간을 줄이는 방법이 있을 거라고 생각했는데 아니나다를까 시간 초과가 발생했다. 코드의 중복도 줄이면서 효율성을 높이려면 어떻게 해야 할까 고민하다가 행뿐만 아니라 열도 누적합을 적용하면 좋을 것 같다고 생각해서 코드를 수정했다.

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int[][] dura = new int[board.length+1][board[0].length+1];
        for(int[] s : skill){
            if(s[0] == 1){
                for(int i=0; i<=s[3]-s[1]; i++){
                    dura[s[1]+i][s[2]] -= s[5];
                    dura[s[1]+i][s[4]+1] += s[5];
                }
            }
            else{
                for(int i=0; i<=s[3]-s[1]; i++){
                    dura[s[1]+i][s[2]] += s[5];
                    dura[s[1]+i][s[4]+1] -= s[5];
                }
            }
        }
        for(int i=0; i<dura.length; i++){
            for(int j=1; j<dura[0].length; j++){
                dura[i][j] += dura[i][j-1];
            }
        }
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                board[i][j] += dura[i][j];
                if(board[i][j] > 0) answer++;
            }
        }
        return answer;
    }
}

 

---

📍최종 코드📍

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int n = board.length;
        int m = board[0].length;
        int[][] dura = new int[n+1][m+1];
        for(int[] s : skill){
            int r1 = s[1];
            int c1 = s[2];
            int r2 = s[3];
            int c2 = s[4];
            int degree = s[5] * (s[0]==1? -1:1);
            
            dura[r1][c1] += degree;
            dura[r1][c2+1] -= degree;
            dura[r2+1][c1] -= degree;
            dura[r2+1][c2+1] += degree;
            
        }
        // 가로
        for(int i=0; i<n+1; i++){
            for(int j=1; j<m+1; j++){
                dura[i][j] += dura[i][j-1];
            }
        }
        
        // 세로
        for(int i=0; i<m+1; i++){
            for(int j=1; j<n+1; j++){
                dura[j][i] += dura[j-1][i];
            }
        }
        
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                board[i][j] += dura[i][j];
                if(board[i][j] > 0) answer++;
            }
        }
        return answer;
    }
}

 

 

📍배운점📍

누적합이 꼭 행으로만 진행되는 게 아닌데 열로 수행해볼 생각은 전혀 못했던 것 같다. 앞으로도 막히는 부분이 있으면 생각의 전환을 하는 연습을 해야 될 것 같다