풀이 방법

문제 이해
- N × M 보드, 각 칸마다 초기 내구도.
- K개의 스킬이 [type, r1, c1, r2, c2, degree] 형태로 주어짐.
  - type = 1(적 공격) → (r1, c1) ~ (r2, c2) 구간의 내구도 degree만큼 감소
  - type = 2(아군 회복) → 해당 구간 내구도 degree만큼 증가
- 스킬이 모두 끝난 뒤, 내구도가 1 이상인 칸의 개수를 세서 반환.
왜 단순 완전탐색(O(K·N·M))이면 안 되는가
- K ≤ 250000, N ≤ 1000, M ≤ 1000 → O(K * N * M) ≤ 2.5 × 10^11 연산 → 시간초과
2차원 차분 배열(diff) + 누적합 아이디어
1. (N+1)×(M+1) 크기의 정수 배열 diff를 모두 0으로 초기화
2. 각 스킬에 대해 “사각형 (r1 .. r2, c1 .. c2)에 +val”을 O(1)로 diff에 기록
  - val = (type==1 ? -degree : +degree)
  - diff[r1][c1] += val;
  - diff[r1][c2+1] -= val; (c2+1 ≤ M)
  - diff[r2+1][c1] -= val; (r2+1 ≤ N)
  - diff[r2+1][c2+1] += val; (r2+1 ≤ N, c2+1 ≤ M)
3. diff 전체에 가로 누적합(행별) 수행
4. for (int i = 0; i <= N; i++) { for (int j = 1; j <= M; j++) { diff[i][j] += diff[i][j-1]; } }
5. diff 전체에 세로 누적합(열별) 수행
6. for (int j = 0; j <= M; j++) { for (int i = 1; i <= N; i++) { diff[i][j] += diff[i-1][j]; } }
7. 이제 diff[i][j]엔 (i, j)에 최종적으로 적용된 “내구도 변화량”이 들어 있으므로,
8. board[i][j] + diff[i][j] 값을 계산해서 1 이상인 칸만 카운트
시간 복잡도: O(K + N * M)
- 스킬 K개를 O(1)씩 기록 → O(K)
- 2차원 누적합 두 번 → O(N * M)
- 최종 카운트 O(N * M)
- → 총합 O(K + N * M)
결과
- Java로도 N ≤ 1000, M ≤ 1000, K ≤ 250000 범위에서 충분히 통과

코드

class Solution {
    
    private int[][] difArray;
    
    public int solution(int[][] board, int[][] skill) {
        
        getDifArray(board.length, board[0].length, skill);
        
        return getAnswer(board);
    }
    
    private void getDifArray(int r, int c, int[][] skill) {
        difArray = new int[r + 1][c + 1];
        
        for(int[] s : skill) {
            int type = s[0];
            int r1 = s[1];
            int c1 = s[2];
            int r2 = s[3];
            int c2 = s[4];
            int degree = s[5];
            
            int value = type == 1 ? -degree : degree;
    
            difArray[r1][c1] += value;
            difArray[r1][c2 + 1] += -value;
            difArray[r2 + 1][c1] += -value;
            difArray[r2 + 1][c2 + 1] += value;
        }
        
        // col prefix sum
        for(int i = 0; i <= r; i++) {
            for(int j = 1; j <= c; j++) {
                difArray[i][j] += difArray[i][j - 1];
            }
        }
        
        // row prefix sum
        for(int i = 1; i <= r; i++) {
            for(int j = 0; j <= c; j++) {
                difArray[i][j] += difArray[i - 1][j];
            }
        }
    }
    
    private int getAnswer(int[][] board) {
        int count = 0;
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                board[i][j] += difArray[i][j];
                
                if(board[i][j] > 0)
                    count++;
            }
        }
        
        return count;
    }
}

저작자표시 (새창열림)