1. 문제 분석

1.1 문제 요약

• N x M 크기의 2차원 건물 배열이 주어집니다.
• 각 건물은 내구도를 가지고 있습니다.
• 여러 개의 스킬(공격/회복)이 직사각형 영역에 적용됩니다.
• 최종적으로 내구도가 1 이상인 건물의 개수를 구해야 합니다.

1.2 제한사항 분석

// 입력 크기
1 ≤ board의 행/열 길이 ≤ 1,000
1 ≤ skill의 행의 길이 ≤ 250,000
1 ≤ degree ≤ 500

• N: 건물의 행 길이
• M: 건물의 열 길이
• K: 스킬의 개수

2. 브루트 포스 접근

2.1 단순 구현

class Solution {
    public int solutionBruteForce(int[][] board, int[][] skills) {
        int answer = 0;
        int height = board.length;
        int width = board[0].length;
        
        // 각 스킬 순회
        for (int[] skill : skills) {
            int type = skill[0];
            int r1 = skill[1], c1 = skill[2];
            int r2 = skill[3], c2 = skill[4];
            int degree = type == 1 ? -skill[5] : skill[5];
            
            // 영향 받는 모든 칸 갱신
            for (int i = r1; i <= r2; i++) {
                for (int j = c1; j <= c2; j++) {
                    board[i][j] += degree;
                }
            }
        }
        
        // 살아남은 건물 카운트
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
}

2.2 시간 복잡도 문제

• O(K × N × M)
  • 각 스킬마다 최대 N × M 칸 순회
• 각 스킬마다 최대 1,000 × 1,000 칸 순회
• 최악의 경우: O(250,000 × 1,000 × 1,000)
• 시간 초과 발생!

3. 차분 배열을 활용한 최적화

• 차분 배열이란 구간 업데이트를 효율적으로 처리하기 위한 기법입니다.
• 차분 배열을 활용하면 구간 업데이트를 O(1)에 처리할 수 있습니다.
• DifferenceArray.md 참고

3.1 핵심 아이디어

1. 차분 배열에 변화량만 기록: O(1)
2. 누적합으로 최종 상태 계산: O(N × M)
3. 원본 배열과 합산하여 결과 도출: O(N × M)
4. 총 시간 복잡도: O(K + N × M)

3.2 최적화된 구현

class Solution {
    public int solution(int[][] board, int[][] skills) {
        int answer = 0;
        int height = board.length;
        int width = board[0].length;
        
        // 차분 배열 초기화 (원본보다 1 크게)
        int[][] differenceArray = new int[height + 1][width + 1];
        
        // 1. 차분 배열에 변화량 기록: O(K)
        for (int[] skill : skills) {
            int type = skill[0];
            int r1 = skill[1], c1 = skill[2];
            int r2 = skill[3], c2 = skill[4];
            int degree = type == 1 ? -skill[5] : skill[5];
            
            // 차분 배열의 적절한 위치에 값 기록
            differenceArray[r1][c1] += degree;        // 시작점
            differenceArray[r1][c2 + 1] -= degree;    // 우측 경계
            differenceArray[r2 + 1][c1] -= degree;    // 하단 경계
            differenceArray[r2 + 1][c2 + 1] += degree;// 대각선 경계
        }
        
        // 2. 2차원 누적합 계산: O(N × M)
        for (int i = 0; i <= height; i++) {
            for (int j = 0; j <= width; j++) {
                if (i > 0) differenceArray[i][j] += differenceArray[i - 1][j];
                if (j > 0) differenceArray[i][j] += differenceArray[i][j - 1];
                if (i > 0 && j > 0) differenceArray[i][j] -= differenceArray[i - 1][j - 1];
            }
        }
        
        // 3. 최종 결과 계산: O(N × M)
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] + differenceArray[i][j] > 0) answer++;
            }
        }
        
        return answer;
    }
}

3.3 코드 설명

1. 차분 배열 생성

   int[][] differenceArray = new int[height + 1][width + 1];
   • 원본보다 1 크게 만들어 경계 처리를 편하게 합니다.

2. 변화량 기록

   differenceArray[r1][c1] += degree;        // 시작점
   differenceArray[r1][c2 + 1] -= degree;    // 우측 경계
   differenceArray[r2 + 1][c1] -= degree;    // 하단 경계
   differenceArray[r2 + 1][c2 + 1] += degree;// 대각선 경계
   • 직사각형 영역의 각 모서리에 적절한 값을 기록합니다.
   • 이후 누적합 계산 시 원하는 영역에만 값이 적용됩니다.

3. 2차원 누적합 계산

   for (int i = 0; i <= height; i++) {
       for (int j = 0; j <= width; j++) {
           if (i > 0) differenceArray[i][j] += differenceArray[i - 1][j];
           if (j > 0) differenceArray[i][j] += differenceArray[i][j - 1];
           if (i > 0 && j > 0) differenceArray[i][j] -= differenceArray[i - 1][j - 1];
       }
   }
   • 2차원 누적합을 계산합니다.
   • 중복 계산을 방지하기 위해 대각선 값을 한 번 빼줍니다.

4. 복잡도 분석

4.1 시간 복잡도 분석

• 각 스킬마다 차분 배열에 변화량만 기록: O(K)
• 누적합으로 최종 상태 계산: O(N × M)
• 원본 배열과 합산하여 결과 도출: O(N × M)
• 총 시간 복잡도: O(K + N × M)
• 최악의 경우: O(250,000 + 1,000 × 1,000) ≈ 1.25 × 10^6
• 브루트 포스 대비 약 200,000배 빠름!

4.2 공간 복잡도

• 원본 배열: O(N × M)
• 차분 배열: O(N × M)
• 총 공간 복잡도: O(N × M)

6. 마치며

• 이 문제는 2차원 차분 배열의 대표적인 활용 사례입니다.
• 직사각형 영역의 업데이트를 O(1)에 처리할 수 있는 차분 배열의 특성을 잘 활용하면, 시간 복잡도를 획기적으로 줄일 수 있습니다.