문제
Programmers Lv3, 파괴되지 않은 건물
핵심
- 입력의 크기가 1,000과 250,000이라 대략 O(N2)이하 알고리즘을 사용한다.
- 스킬에 따라 벽 내구도를 낮추고, 높인다. 마지막에 벽 내구도가 0을 초과하여 부서지지 않은 개수를 반환하면 된다. 최대 1000∗1000 크기의 행렬이고, 스킬 횟수는 최대 250,000까지 가능해서 3중 루프를 이용해서 풀면 당연히 시간초과가 난다.
- 누적 합을 이용하면 벽 내구도를 조작하는 과정을 단순화시켜 O(N2)풀이가 가능하다. 범위에 속하는 모든 값을 변경하는 게 아닌 경계만 검사한다. 예를 들어 (0, 0)에서 (2, 2)의 내구도를 4만큼 깎는다면 아래와 같이 표현할 수 있다.
- 하지만 해당 방식으로는 시간 복잡도를 O(N2)으로 줄일 수 없다. 하지만, 누적합을 이용하면서 각 경계만(4개) 체크해주면 이는 상수시간에 동작하게 된다. 아이디어를 살펴보자. 위의 그림은 아래처럼 나타낼 수도 있다.
- 행과 열 각각에 누적합을 계산하면 아래와 같이 숫자가 채워진다. 먼저 행을 계산하고, 그다음 열을 계산한다.
- 위 아이디어를 코드로 작성하면 아래와 같이 표현할 수 있다.
void do_skill(int type, int r1, int c1, int r2, int c2, int degree) {
degree = type == 1 ? degree * -1 : degree;
cumSum[r1][c1] += degree;
cumSum[r1][c2 + 1] -= degree;
cumSum[r2 + 1][c1] -= degree;
cumSum[r2 + 1][c2 + 1] += degree;
}
- 모든 스킬을 순회하면서 이를 상수 시간에 처리한 후 처음 벽 내구도 상태에 반영하여 부서지지 않은 벽의 개수를 구하면 된다.
개선
코드
C++
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int cumSum[1004][1004];
void do_skill(int type, int r1, int c1, int r2, int c2, int degree) {
degree = type == 1 ? degree * -1 : degree;
cumSum[r1][c1] += degree;
cumSum[r1][c2 + 1] -= degree;
cumSum[r2 + 1][c1] -= degree;
cumSum[r2 + 1][c2 + 1] += degree;
}
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
for (auto s : skill) {
do_skill(s[0], s[1], s[2], s[3], s[4], s[5]);
}
for (int i = 0; i <= board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
cumSum[i][j + 1] += cumSum[i][j];
}
}
for (int j = 0; j <= board[0].size(); ++j) {
for (int i = 0; i < board.size(); ++i) {
cumSum[i + 1][j] += cumSum[i][j];
}
}
int ans = 0;
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] + cumSum[i][j] > 0) ++ans;
}
}
return ans;
}
Java
class Solution {
int[][] cumSum;
void doSkill(int type, int r1, int c1, int r2, int c2, int degree) {
degree = type == 1 ? degree * -1 : degree;
cumSum[r1][c1] += degree;
cumSum[r1][c2 + 1] -= degree;
cumSum[r2 + 1][c1] -= degree;
cumSum[r2 + 1][c2 + 1] += degree;
}
public int solution(int[][] board, int[][] skill) {
int n = board.length;
int m = board[0].length;
cumSum = new int[n + 4][m + 4];
for (var s : skill) {
doSkill(s[0], s[1], s[2], s[3], s[4], s[5]);
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j < m; ++j) {
cumSum[i][j + 1] += cumSum[i][j];
}
}
for (int j = 0; j <= m; ++j) {
for (int i = 0; i < n; ++i) {
cumSum[i + 1][j] += cumSum[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (board[i][j] + cumSum[i][j] > 0) ++ans;
}
}
return ans;
}
}