이번 문제는 프로그래머스의 레벨 3 파괴되지 않은 건물이다.
이 문제는 2022 KAKAO 공채 코딩테스트 문제였다고 한다.
문제를 한 번 차근차근 읽어보도록 하자.
최대 1000 X 1000의 게임보드가 주어지게 된다.
이 때, 특정 사각형 크기의 칸을 파괴하거나 회복시키는 동작이 주어진다.
일련의 동작 이후에 남아있는 칸은 몇 칸일까?
구현
이 로직을 간단히 구현 문제로만 풀면 시간초과가 발생한다.
최악의 경우 1000 X 1000의 게임 보드라고 생각해보자.
동작의 최대 크기인 250,000개가 만약에 주어진다면?
O(1000 X 1000 X 250000)의 시간 복잡도를 가지므로, 시간 초과가 발생한다.
알고 구현했지만, 보기 좋게 시간초과가 발생했다.
어떤 아이디어를 사용해야 시간을 줄일 수 있을까?
2차원 누적합
도저히 아이디어가 떠오르지 않아서 카카오의 공식해설을 찾아보았다.
2차원 누적합을 이용하는 문제라고 한다.
한 번에 아이디어가 이해가 되지 않아 여러번을 읽어야 했다.
기본 원리
예를 들어, 1 2 3 4 5 6과 같은 배열이 존재한다고 생각해보자.
이 때, 문제와 유사하게 0 ~ 4번 까지 2를 더하려고 한다.
그럼 보통은 Brute force를 통해 모든 칸에 2를 더하도록 할 것이다.
하지만, 누적합 개념을 위해 0 0 0 0 0 0으로 동일한 배열을 선언한다.
우리는 해당 배열의 값을 2 0 0 0 0 -2으로 채울 것이다.
왜 이런 값을 채웠을까? 한 번 누적합을 계산해보자.
2 2 2 2 2 0 이라는 배열로 바뀌게 됨을 알 수 있다.
목표로 했던 2를 더하는 동작은 해당 배열 더해서 얻을 수 있다.
즉, 우리는 누적합을 계산하면 일일히 탐색을 할 필요가 없는 것이다!
2차원으로의 적용
그럼 2차원에서는 이 원리를 어떻게 이용할 수 있을까?
예를 들어 아래와 같은 2차원 배열을 생성했다고 해보자.
우리는 (0,0) ~ (2,1)에 3을 더해주고 싶다.
어떻게 해당 배열을 누적합 시킬 수 있을까?
1차원에서 진행했듯, 동일하게 아래와 같이 행을 먼저 계산해보자.
이 배열의 행을 따라 누적합을 진행하면 원하는 칸이 모두 3이 된다.
그럼 여기서 끝내고 위의 배열을 사용하면 될까?
아니다. 더욱 더 간결하게 만들 수 있다.
최종적으로 간결하게 만들면, 위와 같은 배열이 된다.
어떻게 저런 배열이 나오게 되었을까?
위에서 행을 누적합 했던 배열을 다시 한 번 살펴보자.
1열에는 3 3 3과 3열에는 -3 -3 -3이 들어가있다.
어디서 많이 본 형태이지 않은가? 이 형태 또한 누적합 형태로 만들 수 있다.
즉, 3 3 3은 3 0 0 -3으로 -3 -3 -3은 -3 0 0 3으로 만들면
위의 최종적으로 간결해진 배열이 나오게 되는 것이다.
따라서 (x1, y1) ~ (x2, y2)에 대해 우리는 아래의 4개 좌표만 바꾸도록 한다.
(x1, y1)+degree(x1, y2 + 1)+degree(x2 + 1, y1)+degree(x2 + 1, y2 + 1)+degree
최종 구현
주어지는 명령들을 돌며, 단 4개의 좌표에 대한 변화를 dp배열에 기록한다.
명령이 끝나면 dp 배열을 각각 행, 열에 대해 누적합 시킨다.
마지막으로 원래의 board배열과 dp배열을 더하며 발판을 검증한다.
board[i][j] + dp[i][j]가 0보다 크면, 정답에 카운트 해주면 되는 것이다.
이 과정에서 소요되는 시간 복잡도는 단 O(N^2)밖에 걸리지 않는다.
왜? 명령에 대한 수행이 선형적이므로 O(N)의 시간 복잡도를 갖고,
명령 내에서 dp 배열에 값을 더하는 동작이 O(1)의 복잡도를 가지며,
dp 배열의 누적합 동작이 O(N^2)의 복잡도를 가지기 때문이다.
결국 최악의 경우에도 1000 * 1000의 시간 만에 연산이 끝남이 보장된다.
최종적으로 아래와 같이 구현되었다.
int dp[1001][1001];
void input_coefficient(int x1, int x2, int y1, int y2, int coef) {
dp[x1][y1] += coef;
dp[x2 + 1][y1] -= coef;
dp[x1][y2 + 1] -= coef;
dp[x2 + 1][y2 + 1] += coef;
}
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
for (auto info : skill) {
int x1 = info[1];
int y1 = info[2];
int x2 = info[3];
int y2 = info[4];
if (info[0] == 1)
input_coefficient(x1, x2, y1, y2, info[5] * -1);
else
input_coefficient(x1, x2, y1, y2, info[5]);
} // 여기서 dp 배열에 누적합 계수를 모두 저장한다.
for (int i = 0; i <= board.size(); i++)
for (int j = 1; j <= board[0].size(); j++)
dp[i][j] += dp[i][j - 1];
for (int j = 0; j <= board[0].size(); j++)
for (int i = 1; i <= board.size(); i++)
dp[i][j] += dp[i - 1][j];
// 위의 두 for문이 누적합 계수를 만드는 과정
for (int i = 0; i < board.size(); i++)
for (int j = 0; j < board[0].size(); j++)
if (board[i][j] + dp[i][j] > 0)
answer++;
// 최종적으로 남은 계수들을 더했을 때 살아있는 지형 카운트
return answer;
}