[Programmers] 파괴되지 않은 건물 (카카오 2022 공채)

[문제 링크]

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

프로그래머스

 

 

[효율성 실패 코드]

import java.util.*;

class Solution {
    int[][] board;
    public int solution(int[][] board, int[][] skill) {
        // board 건물 내구도
        // skill -> type = 1 -> 공격
        // skill -> type = 2 -> 회복
        // skill -> [type, r1, c1, r2, c2, degree]
        // (r1, c1) -> (r2, c2) 까지 degree 만큼 공격이나 회복
        
        // 전역변수 처리
        this.board = board;
        
        for(int[] s : skill) {
            int type = s[0];
            int startX = s[1];
            int startY = s[2];
            int endX = s[3];
            int endY = s[4];
            int degree = s[5];
            
        
            if(type == 1) {
                // 공격
                attack(startX, startY, endX, endY, degree);
            } else if(type == 2) {
                // 힐
                heal(startX, startY, endX, endY, degree);
            }
        }
        
        
        int answer = getWall();
        
        return answer;
    }
    
    
    // 부서지지 않은 벽 갯수 세는 함수
    public int getWall() {
        int x = board.length;
        int y = board[0].length;
        
        int wallCount = 0;
        
        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                if(board[i][j] > 0) {
                    wallCount++;
                }
            }
        }
        
        return wallCount;
    }
    
    // 공격하여 board 변경하는 함수
    public void attack(int sx, int sy, int ex, int ey, int d) {
        // 하나만 공격한다면
        if(sx == ex && sy == ey) {
            board[sx][sy] -= d;
            return;
        } 
        
        
        for(int i = sx; i <= ex; i++) {
            for(int j = sy; j <= ey; j++) {
                board[i][j] -= d;
            }
        }
    }
    
    
     // 힐하여 board 변경하는 함수
    public void heal(int sx, int sy, int ex, int ey, int d) {
        // 하나만 힐한다면
        if(sx == ex && sy == ey) {
            board[sx][sy] += d;
            return;
        } 
        
        
        for(int i = sx; i <= ex; i++) {
            for(int j = sy; j <= ey; j++) {
                board[i][j] += d;
            }
        }
    }
}

 

[정답 코드]

import java.util.*;

class Solution {
    // 누적합을 하기 위한 배열
    int[][] grid;
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;

        // 누적합을 사용하려면 크기가 하나씩 더 큰걸 사용하는게 편함
        grid = new int[board.length+1][board[0].length+1];

        for(int[] s : skill) {
            int type = s[0]; // 1 공격 2 힐
            int startX = s[1];
            int startY = s[2];
            int endX = s[3];
            int endY = s[4];
            int degree = s[5];

            if(type == 1) {
                changeGrid(startX, startY, endX, endY, degree * -1);
            } else {
                changeGrid(startX, startY, endX, endY, degree);
            }
        }

        // 가로 계산
        for(int i = 0; i < grid.length-1; i++) {
            for(int j = 1; j < grid[0].length-1; j++) {
                grid[i][j] += grid[i][j-1];
            }
        }

        // 세로 계산
        for(int j = 0; j < grid[0].length-1; j++) {
            for(int i = 1; i < grid.length-1; i++) {
                grid[i][j] += grid[i-1][j];
            }
        }
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                grid[i][j] += board[i][j];
            }
        }

        return countWall();
    }

    public void changeGrid(int sx, int sy, int ex, int ey, int d) {
        if(sx == ex && sy == ey) {
            grid[sx][sy] += d;
            grid[sx+1][sy] += (-1 * d);
            grid[sx+1][sy+1] += (-1 * d);
            grid[sx][sy+1] += d;

            return;
        }

        grid[sx][sy] += d;
        grid[ex+1][sy] += (-1 * d);
        grid[sx][ey+1] += (-1 * d);
        grid[ex+1][ey+1] += d;
    }

    public int countWall() {
        int count = 0;

        for(int i = 0; i < grid.length-1; i++) {
            for(int j = 0; j < grid[0].length-1; j++) {
                if(grid[i][j] > 0) {
                    count++;
                }
            }
        }

        return count;
    }
}

 

 

[회고]

처음에 뭔가 쉬워보여서 무작정 구현을 했는데 테스트만 통과하고 효율성 테스트에서 다 실패했다..

 

효율성이 0이라니..

근데 아무리 생각해도 풀이가 떠오르지 않아 답을 보고 또 하나 배우게 되었다..

 

이 문제는 누적합 알고리즘을 모르면 풀 수가 없다.

1차원 배열의 누적합은 바로 이해가 됐지만

2차원 누적합이라 조금 이해가 처음엔 힘들었지만 해보니 할만했다.

이런거 혼자풀 수 있을때까지 화이팅

 

 

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.