[2022 KAKAO BLIND RECRUITMENT] 파괴되지 않은 건물

[2022 KAKAO BLIND RECRUITMENT] 파괴되지 않은 건물

🙋‍♂️ 들어가며

이번 문제는 단순한 반복문으로 접근하면 시간초과가 나는 문제였다.

최악의 경우 1000 * 1000 * 25000이기에 무조건 시간초과다.

그래서 누적합을 사용해야했다 차변을 사용한 누적합 말이다.

🤔누적합이 무엇인가??

편의상 차변 추가를 위해 새로운 diff 배열은 [row + 1][col + 1] 로 만들자

0,0 ~ 3,4까지 (v = -4) 만큼 채우고싶다.

-4	0	0	0	0	+4
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
+4	0	0	0	0	-4

열방향, 행방향에 더이상 퍼지는 것을 막기위해 테두리의 er+1, ec+1에 각각 -v를 추가했다.

근데 굳이 여기서 diff[er+1][ec+1] = v 를 왜 추가해야할까??

그 이유는 행과 열의 누적합을 2단계로 계산하면 알게된다.

먼저 행계산

1️⃣ 행계산

-4	-4	-4	-4	-4	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
+4	+4	+4	+4	+4	0

그 이후 열계산

2️⃣ 열계산

-4	-4	-4	-4	-4	0
-4	-4	-4	-4	-4	0
-4	-4	-4	-4	-4	0
-4	-4	-4	-4	-4	0
0	0	0	0	0	0

⭐오오오

원하는대로 0,0 ~ 3,4까지 -4가 전부 채워졌군

이제 DP 누적합에 대해 알았으니 본격적으로 풀이를 시작하도록 하겠다.

풀이

testcase 1번 기준으로 skill은 4회다.

0번째 skill -> 0,0 ~ 3,4까지 -4만큼 공격

1번째 skill -> 2,0 ~ 2,3까지 -2만큼 공격

2번째 skill -> 1,0 ~ 3,1까지 +2만큼 회복

3번째 skill -> 0,1 ~ 3,3까지 -1만큼 공격

위는 0번째 공격을 하여 diff만큼 배열에 값을 추가했다.

근데 편의상 마지막에 계산할때는 검은색으로 칠한 테두리의 영역은 보지 않아도 될 것 같다.

아무튼 이어서 1,2,3 번째 skill을 시전하면 다음 사진과 같아진다.

먼저 행계산부터, 그 이후 열계산

1️⃣ 행계산

-4	-5	-5	-5	-4	0
2	2	0	0	0	0
-2	-2	-2	-2	0	0
2	2	2	2	0	0
+2	+1	+1	+1	+0	-4

2️⃣ 열계산

-4	-5	-5	-5	-4	0
-2	-3	-5	-5	-4	0
-4	-4	-7	-7	-4	0
-2	-3	-5	-5	-4	0
0	-2	-4	-4	-4	-4

여기서 의아할 것이다.

아니? 누적합하면 테두리의 경계까지 다 합산 했을때 0이 나와야하는데 왜 테두리가 0이 아니지??

1차원 누적은 배열 마지막이 항상 0으로 돌아온다.

그러나 2차원은 테두리가 0이 아닐 수 있으므로 내가 잘못 구했다고 생각하지말자.

참 아까 검은 테두리 영역은 필요없다고 했으니 4*5 영역만 누적합 영역만 다시 보겠다

행 계산을 하면 아래와 같다

1️⃣ 행계산

-4	-5	-5	-5	-4
2	2	0	0	0
-2	-2	-2	-2	0
2	2	2	2	0

다음은 열계산이다

2️⃣ 열계산

-4	-5	-5	-5	-4
-2	-3	-5	-5	-4
-4	-4	-7	-7	-4
-2	-3	-5	-5	-4

이제 이 상태에서 완전탐색을 통해

arr[r][c] + diff[r][c] > 0 -> cnt++

이렇게 구해주면 되겠다

이것의 시간복잡도는 다음과 같겠다

O(T + (row * col) )

즉 O(250,000 + 1,000,000)

✅ 코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int cnt = 0;
        
        int row = board.length;
        int col = board[0].length;
        
        // 차분을 이용하자
        // 이후 마지막 idx인 row, col은 이용하지않는다
        // idx는 누적합시 row-1, col-1 까지만 이용하자
        long[][] diff = new long[row+1][col+1];
        
        
        int T = skill.length;
        for (int t = 0; t < T; t++) {
            int type = skill[t][0];
            int sr = skill[t][1];
            int sc = skill[t][2];
            int er = skill[t][3];
            int ec = skill[t][4];
            int degree = skill[t][5];
            
            // 공격일때 음수처리
            if (type == 1) {
                degree = -degree;
            }
            
            // 1-1. 왼쪽 맨위끝 모서리
            diff[sr][sc] += degree;
            
            // 1-2. 왼쪽 맨위 우측끝 모서리
            diff[sr][ec+1] += -degree;
            
            // 1-3. 왼쪽 맨아래 맨밑 모서리
            diff[er+1][sc] += -degree;
            
            // 1-4. 맨 오른쪽 밑 끝 모서리
            diff[er+1][ec+1] += degree;
        }
        
        
        // 2. 행방향 누적합
        for (int r = 0; r < row; r++) {
            for (int c = 1; c < col; c++) {
                diff[r][c] += diff[r][c-1];
            }
        }
        
        // 3. 열방향 누적합
        for (int r = 1; r < row; r++) {
            for (int c = 0; c < col; c++) {
                diff[r][c] += diff[r-1][c];
            }
        }
        
        // 4. 결과
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (board[r][c] + diff[r][c] > 0) cnt++;
            }
        }
        
        return cnt;
    }
}