[알고리즘 TIL] 파괴되지 않은 건물

문제

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

프로그래머스

프로그래머스 lv3. 누적합

설명

단순히 정확성을 통과하기 위해서라면 3중 반복문을 통해 구현할 수 있다. 하지만 250,000(skill) * 1,000(row) * 1,000(col) = 약 2,500초.. 이기 때문에 효율성은 하나도 통과하지 못한다.

도저히 내 머리로는 풀 수 없어서 카카오 풀이(https://tech.kakao.com/posts/488)를 참고해보니, 누적합을 통해 해결했다.

 

먼저 1차원 배열에서 효과적으로 처리할 수 있는 방법을 생각해보자.

[1,2,4,8,9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야하는 상황이라고 가정하자. O(N)의 시간복잡도를 O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 것이다. [-2,0,0,0,2] 라는 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되기 때문에 초기 배열과 더해주면 [-1,0,2,6,9] 즉, 원하는 결과를 얻을 수 있다. 즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 된다. 

=> 즉, 1차원 배열에 대해 여러 번의 감소와 증가가 진행되면, 2중 반복문을 1중 반복문으로 줄일 수 있다. 핵심은 변경을 따로 저장해두고, 나중에 한번에 계산!

 

이 문제는 이 아이디어를 2차원 배열로 확장해줘야한다. 배열의 행만 따로 봐서 위에 설명한 아이디어를 하나의 행씩 적용시키면, 다음과 같이 된다.

위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화가 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -n만큼의 변화가 같은 것을 볼 수 있다. 이를 2차원 배열에 적용시키면 다음과 같다. 

위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합하면(2중 반복) 처음의 의도와 같이 배열이 나오는 것을 확인할 수 있다. 

 

풀이법이 되게 신기했고 감탄스럽다... 꼭 체화시키도록 하자.

구현

import java.util.*;

class Solution {
    
    public static int[][] sums;
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int r = board.length;
        int c = board[0].length;
        sums = new int[r+1][c+1]; //누적합은 +1씩 배열 생성!
        
        for(int[] s:skill){
            int type = s[0];
            if(type == 1){
                sums[s[1]][s[2]] -= s[5];
                sums[s[3]+1][s[2]] += s[5];
                sums[s[1]][s[4]+1] += s[5];
                sums[s[3]+1][s[4]+1] -= s[5];
            } else {
                sums[s[1]][s[2]] += s[5];
                sums[s[3]+1][s[2]] -= s[5];
                sums[s[1]][s[4]+1] -= s[5];
                sums[s[3]+1][s[4]+1] += s[5];
            }
        }
        

        // 위 -> 아래
        for(int j=0;j<c+1;j++){
            for(int i=0;i<r;i++){
                sums[i+1][j] += sums[i][j];
            }
        }
        

        // 왼 -> 오른
        for(int i=0;i<r+1;i++){
            for(int j=0;j<c;j++){
                sums[i][j+1] += sums[i][j];
            }
        }
        
        
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(board[i][j] + sums[i][j] > 0) answer++;
            }
        }
        
        return answer;
    } 
}