[프로그래머스LV3] 파괴되지 않은 건물

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

프로그래머스

 

누적합은 현재 배열에서 각 인덱스별로 누적된 합들을 간편하게 계산하고 사용할 수 있는 알고리즘이다. 

 

그러나 이것을 응용하면 범위의 빈도수도 파악이 가능하다. 무슨말이냐하면

 

만약 1~10까지 숫자가 존재한다고 할 때

 

1~4, 2~5 두개가 주어진다고 하자. 그렇다면 

1 -> 1

2 -> 2

3 -> 2

4 -> 2

5 -> 1

 

번 씩 범위에 포함된 것을 알 수 있다. 이것을 일일히 확인하면 첫번째 1~4가 들어왔을 때 전부 체크하면서 4번, 2~5 확인하면서 3번으로 N + M 번시간이 걸리고 만약 1억이라고 치면 엄청난 시간이 걸려버린다.

 

하지만 누적합을 사용하면

 

시작점에 1을 박아두고 끝나는 지점 + 1 지점에 -1을 박아놓고 누적합하면

 

1 1 1 1 0 0 0 0 처럼 한번에 확인할 수 있다. 그래서 총 O(N)으로 모든 빈도수를 파악 가능하다.

 

이 문제는 이 방식을 2차원으로 옮겨놓은 것과 같다.

 

#include <string>
#include <vector>

using namespace std;
int boom[1001][1001];
int prefix[1001][1001];
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    int N = board.size();
    int M = board[0].size();
    
    for(int i = 0; i < skill.size(); i++){
        int type = skill[i][0];
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        int degree = skill[i][5];
        
        if(type == 1) degree *= -1;
        
        boom[r1][c1] += degree;
        boom[r2 + 1][c2 + 1] += degree;
        boom[r1][c2 + 1] -= degree;
        boom[r2 + 1][c1] -= degree;
    }
    
    for(int i = 1; i < N + 1; i++){
        for(int j = 1; j < M + 1; j++){
            prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] + boom[i - 1][j - 1] - prefix[i - 1][j - 1];
        }
    }
    
    for(int i = 1; i < N + 1; i++){
        for(int j = 1; j < M + 1; j++){
            if(board[i - 1][j - 1] + prefix[i][j] > 0) answer++;
        }
    }
    
    return answer;
}