[프로그래머스] 카카오_파괴되지 않은 건물 (자바 풀이)

문제

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

코딩테스트 연습 - 파괴되지 않은 건물

 

풀이

이 문제는 정말 재밌는 문제였다. 문제에 나온대로 그냥 덧셈을 모두 하게 되면 시간초과가 발생할 수 밖에 없다.

N*M배열에 K개의 명령이 있을 때 O(KNM)이라는 시간복잡도가 발생하기 때문이다.

 

따라서 시간복잡도를 줄여야 효율성 테스트를 통과할 수 있다. 어떻게 하면 효율적으로 값을 구할 수 있을까??

 

정답은 누적합이다.

 

예를 들어 4*4 배열에서 (0,0) ~ (2,2) 까지 n을 더하고 싶다고 하자.

 

[ n, 0, 0, -n]

[ 0, 0, 0,  0]

[ 0, 0, 0,  0]

[-n, 0, 0, n]

 

이런 식의 누적합 배열에 n을 배치해주면 된다.

 

즉,

 

(r1,c1)=n 

(r1, c2+1)= -n

(r2+1, c1) = -n

(r2+1, c2+1) = n

 

이렇게 배치해주고, 가로 누적합과 세로 누적합을 구해주면 된다.

 

먼저 가로 누적합을 구해보면 다음과 같다.

 

[ n,  n,  n,  0]

[ 0,  0,  0,  0]

[ 0,  0,  0,  0]

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

 

이후 세로 누적합을 구해보면 다음과 같다.

 

[ n,  n,  n,  0]

[ n,  n,  n,  0]

[ n,  n,  n,  0]

[ 0,  0,  0,  0]

 

정확히 (0,0)~(2,2)에 n이 더해진 것을 확인 할 수 있다.

 

이처럼 모든 좌표에서 누적합을 구해준 다음, 마지막에 board 배열에 누적합 배열을 더해주면 된다.

 

이때 주의해야 할점은, 모든 배열의 원소가 0으로 초기화된 preSum[][] 배열을 따로 만들어서 누적합을 계산해줘야 한다는 것이다. 또한, r2+1, c2+1 까지 계산할 수 있어야 하므로 기존 board 배열보다 가로 세로 길이가 1만큼 더 커야한다.

 

자세한 내용은 코드를 참고하자.

 

 

코드

 

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 preSum[][] = new int[N+1][M+1]; // 누적합 배열은 size가 1 더 큼
        
        for(int i=0; i<skill.length; i++){
            int type = skill[i][0];
            int r1 = skill[i][1], c1 = skill[i][2];
            int r2 = skill[i][3], c2 = skill[i][4];
            int degree = skill[i][5];
            
            if(type == 1){  // destroy
                preSum[r1][c1] += -degree;
                preSum[r2+1][c1] += degree;
                preSum[r1][c2+1] += degree;
                preSum[r2+1][c2+1] += -degree;
            }else{  // repair
                preSum[r1][c1] += degree;
                preSum[r2+1][c1] += -degree;
                preSum[r1][c2+1] += -degree;
                preSum[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 += preSum[i][j];
                preSum[i][j] = sum;
            }
        }
        
        /* 세로 누적합 계산*/        
        for(int i=0; i<M; i++){
            int sum = 0;
            for(int j=0; j<N; j++){
                sum += preSum[j][i];
                preSum[j][i] = sum;
            }
        }
        
        /* count */
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(preSum[i][j] + board[i][j] > 0 ) answer++;
            }
        }                   
        
        return answer;
    }
    
}

 

재밌는 문제였다.