직관적으로, board를 순회하면서 각 skill의 크기에 맞게 값을 더해주면서 풀게되면 Worst case의 시간복잡도가 O(N*M*K) = 1,000 * 1,000 * 250,000 = 250,000,000,000 으로 효율성이 천장을 뚫어버리게 된다.
따라서 구간의 합을 쉽게 해주는 누적합을 떠올릴 수 있다.
누적합이란 말 그대로, 배열을 순회하면서 누적된 값을 해당 배열에 더해주는 방법이다.
예를들어, [1,2,3,4,5] 배열에 2 - 4번 index에 2를 더해주고 1 - 3에 4를 더해준다고 해보자. 이때 누적합을 이용하면, 누적합을 위한 배열을 선언하고, 구간의 시작과, 끝 다음에 해당 배열의 2번, 5번 index에는 +2, -2를, 1번, 3번 index에는 4, -4를 더해준다.
이때 두 배열을 더할때는 단순히 index에 대응되는 값들을 더해주는 것이 아니라, 누적합에 대한 배열은 앞에서 부터 값들을 누적한 값을 원래 배열에 더해주어야 한다.
누적합
이렇게 되면 배열의 크기가 N일때, 구간에 대한 합을 O(N)이 아닌, O(1)로 처리할 수 있다는 장점이 있다. (두개의 인덱스 - 시작과 끝 다음 인덱스에만 접근하면 되므로)
위 문제는 누적합을 이용하면 쉽게 풀 수 있다. 하지만 2차원 배열이 주어지기 때문에 2차원에 대한 누적합을 사용해야 한다. 2차원 누적합을 구현하는 아이디어는 생각보다 간단하다. 행, 열에 대해 각각 두번의 누적합을 진행해주면 된다.
누적합의 핵심만 기억하고 있으면 된다. 바로 시작과 끝 다음 인덱스에 접근한다는 것이다!
예를들어 5,5 크기의 board에서 (1,1) ~ (2, 3)에 2를 더해준다고 해보자. 이때 누적합에 대한 배열을 생각해 보면, 다음과 같은 접근이 가능할 것이다. 우선 위에 1차원 누적합에서 했던 방식과 똑같이 행을 기준으로, 모든 행에 대해 누적합을 해주는 것이다.
모든 행에 대해 누적합을 진행
이 방식으로도 구현이 되겠지만, 2, 0, -2가 중복되고 있다. 조금 더 최적화할 수 있을 거라는 확신이 든다. 만약 누적합 방식을 행에 대해 한번, 열에 대해 한번, 총 두 번을 진행하게 된다면 어떨까?
행에 대해 한번, 열에 대해 한번 누적합을 진행
1번 방식과 달리 이제, 마지막 열 다음에 각각 -2와 2를 추가해주었다. 이제 행에 대해 누적합을 진행하고, 그 다음 결과에서 열에 대해 누적합을 진행해주면 결국 1번 방식과 같은 결과를 얻을 수 있다!
(좌) 행에 대해 누적합 진행, (우) 열에 대해 누적합 진행
누적합을 떠올리되, 2차원에서 사용할 수 있는 누적합 방법에 대해 생각해볼 수 있는 문제였다.
정답
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
int n = board.size();
int m = board[0].size();
vector<vector<int>> acc = vector<vector<int>>(n+1, vector<int>(m+1, 0));
for(int i=0; i<skill.size(); i++)
{
auto sk = skill[i];
int type = sk[0];
int r1 = sk[1];
int c1 = sk[2];
int r2 = sk[3];
int c2 = sk[4];
int degree = sk[5];
if(type==1)
{
degree = -degree;
}
acc[r1][c1] += degree;
acc[r1][c2+1] += -degree;
acc[r2+1][c1] += -degree;
acc[r2+1][c2+1] += degree;
}
for(int i=0; i<n; i++)
{
int sum = 0;
for(int j=0; j<m; j++)
{
sum += acc[i][j];
acc[i][j] = sum;
}
}
for(int i=0; i<m; i++)
{
int sum = 0;
for(int j=0; j<n; j++)
{
sum += acc[j][i];
acc[j][i] = sum;
}
}
int count = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
board[i][j] += acc[i][j];
if(board[i][j] > 0)
count++;
}
}
answer =count;
return answer;
}
