파괴되지 않은 건물(프로그래머스) JAVA

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

프로그래머스

 

• 적은 건물을 공격할수 있다. 내구도가 0이하가 되면 파괴된다.
• 아군은 회복 스킬을 사용하여 건물의 내구도를 높일 수 있다.

이런 상태가 있을 때, (0,0)부터 (3,4)까지 공격하여 4만큼 내구도를 낮추면 

이렇게 변경된다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

이러면 건물 4개가 파괴 된 것이다.

계속 진행을 하면 최종 상태가 이렇게 된다. 결국 파괴된 건물은 10개가 존재한다!!

입력은 이렇게 주어진다. 2차원 배열이 주어진다.

skill은 1일때는 공격 2일 때는 회복이다. 1, 0, 0, 3, 4, 4는  (0,0) 부터 (3,4) 까지 4의 데미지를 준다는 뜻이다.

참고로 이 문제는 2022 KAKAO BLIND RECRUITMENT 6번문제였다.

 

문제에 대한 아이디어

제일 처음 든 생각은 브루트포스로 푸는것 처럼 (0,0) 부터 (3,4) 까지 돌면서 4를 내리고 마지막에 결과를 조사하면 되지 않을까였다.

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

이렇게 브루트 포스로 모든 지점을 돌면서 공격하거나 회복시키고 마지막에 0보다 큰 건물의 갯수를 카운트 했다.

결과는 효율성 테스트에서 모두 시간 초과가 나왔다. 당연한 결과 였다. 위의 코드의 시간복잡도를 계산해보면 N을 skill 횟수라고 하고 M,K를 2중 for문이라고 하면 O(N*M*K) 라는 결과가 나온다. 당연히 시간초과가 걸릴 것이다.

 

누적합으로 풀기

이 문제를 쉽게 풀 수 있는 방법이 누적합으로 푸는 것이다.

누적합을 2차원 배열에 적용하면 된다. 

 

• 1차원 배열에서 누적합을 어떻게 사용할까?

[1,2,4,8,9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 하면 모든 지점을 돌면서 빼는것이 아닌 새로운 배열을 만드는 것이다. 새로운 배열은 [-2, 0, 0, 0, 2] 를 저장한다. 3번째가 아닌 4번째에 빼고 싶은 수의 반대 부호를 주는 것이다. 이제 이 배열을 앞에서부터 누적합 하면 [-2, -2, -2, -2, 0]이 된다. 그 후 새로운 배열에 더해주면 된다.

이렇게만 보면 똑같이 for문을 도는 것이 아닌가라는 의문이 들지만 누적합을 해야할 부분이 많다고 생각해보면 된다.

0부터 3까지 2를 빼고 1 부터 5 까지 1을 더해라 하면 [-2,1,0,0,2,0,-1] 이렇게 배열을 만들고 누적합을 해주면 된다. 즉 O(N) 시간에 했던 누적합을 O(1) 시간에 해결해줄 수 있다. 

 

• 2차원 배열에 적용하기

예를 들어 (0,0) 부터 (3,4) 까지 2를 빼야한다고 생각하자. 다른 2차원 배열을 하나 만드는 것이다.

-2 0 0 0 2  
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 0 0 0 -2

이렇게 만드는 것이다. (0,0) (0,5) (4,0) (4,5) 에 수를 집어 넣고 (0,0) 시작하는 부분은 뺄 숫자나 더할 숫자에 따라 부호를 선택해준다.

이제 이 배열을 가로로 누적합 한번 세로로 누적합 한번 해주면 된다. (참고로 순서는 상관이 없다)

//가로로 한번 누적합
-2 -2 -2 -2 0  
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 2 2 2 0

//세로로 한번 누적합
-2 -2 -2 -2 0  
-2 -2 -2 -2 0
-2 -2 -2 -2 0
-2 -2 -2 -2 0
0 0 0 0 0

결국 (0,0)에서부터 (3,4)까지 얼마나 빼야하는지 알려준다!!!

 

구현

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        //누적합 계산할 배열
        int pro[][] = new int[board.length+1][board[0].length+1];
        for(int i = 0; i< skill.length; ++i){
            int ca = skill[i][0];
            int starty = skill[i][1];
            int startx = skill[i][2];
            int endy = skill[i][3];
            int endx = skill[i][4];
            int power = skill[i][5];
            //공격할 경우
            if(ca == 1){
                pro[starty][startx] -= power;
                pro[starty][endx+1] += power;
                pro[endy+1][startx] += power;
                pro[endy+1][endx+1] -= power;
            }
            //회복할 경우
            else{
                pro[starty][startx] += power;
                pro[starty][endx+1] -= power;
                pro[endy+1][startx] -= power;
                pro[endy+1][endx+1] += power;
            }
        }
        // 세로로 누적합
        for(int y = 1; y <pro.length; ++y){
            for(int x = 0; x<pro[0].length; ++x){
                pro[y][x] += pro[y-1][x];
            }
        }
        //가로로 누적합
        for(int x =1; x<pro[0].length; ++x){
            for(int y = 0; y<pro.length; ++y){
                pro[y][x] += pro[y][x-1];
            }
        }
        //0보다 큰거 count
        for(int i=0; i<board.length; ++i){
            for(int j=0; j<board[i].length; ++j){
                if(board[i][j] + pro[i][j] > 0) ++answer;
            }
        }
        
        return answer;
    }
}