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

해설

skill로 주어진 구역을 degree 만큼 회복/공격하여 최종 값이 1 이상인 칸수를 구하는 문제이다.

 

가장 쉽게 떠오르는 풀이는 skill 의 정보가 하나씩 주어질 때마다 (r1, c1)부터 (r2, c2)까지의 구역을 순회하며 degree만큼 빼거나 더하는 방법이다. 하지만 이렇게 구현하면, 시간 복잡도는 O(skill.size() x N x M) 이 되어 TLE 가 발생한다. 따라서 다른 방법을 찾아야 하는데 이 문제는 누적합을 이용하면 쉽게 해결할 수 있다.

 

예를 들어,  (0, 0)부터 (2, 2)까지 영역에 n만큼을 더하려면 다음과 같은 배열을 만들면 된다.

 

n 0 0 -n

0 0 0 0

0 0 0 0

-n 0 0 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

 

즉, (r1, c1)부터 (r2, c2)까지 영역에 n만큼을 더하려면 (r1, c1)에 n, (r1, c2+1)에 -n, (r2+1, c1)에 -n, (r2+1, c2+1)에 n을 적은 배열을 만들고 좌우, 상하 방향으로 누적합을 구해 각각의 자리를 board와 더해주면 된다.

 

정리해보면, 해당 문제는 다음 순서로 해결할 수 있다.

1) skill을 순회하며 (r1, c1), (r1, c2+1), (r2+1, c1), (r2+1, c2+1)에 각각 degree과 -degree을 기록해놓는다.

2) skill을 모두 순회한 후 왼쪽 방향에서 오른쪽 방향으로, 위에서 아래로 누적합을 구한다.

3) 누적합 배열을 board 값들과 더한다. 최종 board 값이 1 이상인 칸의 개수를 세서 리턴하면 정답이다.

누적합을 사용하면 O(skill.size() + N x M)에 문제를 해결 가능하다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    
    int n = board.size();
    int m = board[0].size();
    
    vector<vector<int>> pfx(n+1, vector<int>(m+1, 0));
    
    for (const auto& v : skill) {
        int type = v[0], r1 = v[1], c1 = v[2], r2 = v[3], c2 = v[4], d = v[5];
        if (type == 1) d *= -1;
        pfx[r1][c1] += d;
        pfx[r1][c2+1] += -d;
        pfx[r2+1][c1] += -d;
        pfx[r2+1][c2+1] += d;
    }
    
    for (int i=0; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            pfx[i][j] += pfx[i][j-1];
        }
    }
    
    for (int j=0; j<=m; j++) {
        for (int i=1; i<=n; i++) {
            pfx[i][j] += pfx[i-1][j];
        }
    }
    
    int cnt = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            board[i][j] += pfx[i][j];
            if (board[i][j] >= 1) cnt++;
        }
    }
    
    return cnt;
}