[pro] 프로그래머스 level3 92344 파괴되지 않은 건물 - dp, 배열 누적합

[문제]

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

프로그래머스

 

[풀이]

문제 자체는 풀기 쉽지만 단순하게 풀면 O(NM)의 시간복잡도를 가져 효율성 테스트를 절대 통과할 수 없다.

효율성을 따지는 문제의 경우 그래프가 아니라면 dp나 이분탐색으로 풀 수 있는지를 떠올리는데, 이 문제같은 경우 2차원 배열에 균일한 변화량을 똑같이 더해주거나 빼주기 때문에 dp를 이용한 이차원 배열 누적합 문제임을 알 수 있다.  

 

2차원 배열 누적합을 구하는 방법은 다음과 같다.

1) skill 배열 포인트 마킹하기

예를 들어 4*4 배열에서 (0,0) ~ (2,2) 까지 n을 더하고 싶다면 다음과 같이 마킹해야 한다.

[n  0 0 -n]

[0  0 0  0]

[0  0 0  0]

[-n 0 0  n]

 

(r1, c1) = n

(r1, c2+1) = -n

(r2+1, c1) = -n

(r2+1, c2+1) = n

 

2) 가로 누적합 구하기

[n  n  n  n-n(=0)]            

[0  0  0  0]

[0  0  0  0]

[-n -n -n -n+n(=0)]

 

3) 세로 누적합 구하기

[n  n  n  0]                 

[n  n  n  0]                 

[n  n  n  0]                  

[n-n n-n n-n 0]         

 

(0,0) ~ (2,2) 가지 n이 더해졌다. 이런 방식으로 누적합 배열을 구하면 O(N+M)의 복잡도를 가지며, 이후 원래의 board와 더해주면 최종 board가 된다.

 

다른 분의 풀이 참고

https://yamyam-spaghetti.tistory.com/75

 

[코드]

 

class Solution {
    int[][] pre_sum;
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        // 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return
        int n = board.length;
        int m = board[0].length;
        
        pre_sum = new int[n+1][m+1];
         
        //skill - type, r1, c1, r2, c2, degree
        //type 1- 적의 공격 2 - 회복


        //skill 포인트 마킹
        for(int[] s: skill){
            int type = s[0];
            int r1=s[1]; int c1=s[2];
            int r2=s[3]; int c2=s[4];
            int degree;
            if(type==1){
                degree = -1*s[5];
            }
            else degree = s[5];
            
            pre_sum[r1][c1] += degree;
            pre_sum[r2+1][c1] -= degree;
            pre_sum[r1][c2+1] -= degree;
            pre_sum[r2+1][c2+1] += degree;
        }
        
        //가로 누적합 
        for(int i=0; i<n+1; i++){
            int sum = 0;
            for(int j=0; j<m+1; j++){
                sum += pre_sum[i][j];
                pre_sum[i][j] = sum;
            }
        }
        
        //세로 누적합 
        for(int i=0; i<m; i++){
            int sum = 0;
            for(int j=0; j<n; j++){
                sum += pre_sum[j][i];
                pre_sum[j][i] = sum;
            }
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(pre_sum[i][j]+board[i][j] >= 1){
                    answer++;
                }
            }
        }
        
        return answer;
    }

}