프로그래머스: 파괴되지 않은 건물(lv2) [Java] - 포포

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

---

이 문제는 정확도 + 효율성 두 가지를 요하는 문제다.
행렬 N*M에 Skill을 퍼붓는데, 

• 1<= N <=1000,  1<= M <=1000
• 1 ≤ skill 개수 ≤ 250,000

이 조건에서 N*M의 행렬을 250,000번 탐색하게 된다면 효율성을 통과할 수 없는 문제다.

따라서 누적합을 이용해 Skill을 퍼부은 결과를 저장한다음, 그 결과를 원래 행렬에 더해주어야 한다. 

중요한 점은 누적합을 구할 때, 입력 받은 Skill마다 누적합 연산을 하는 것이 아니라
입력 받은 Skill들을 누적합 배열에 마킹해두었다가 마지막 한 번에 누적합 연산을 실행해야 한다는 점이다.

누적합 배열에 마킹한 뒤, 한 번에 연산하는 방법은 아래 그림과 함께 설명한다.

---

아래 5 * 5 크기의 map이 있으며 각 건물의 내구도가 모두 5로 주어진 상황이다.

1. (1,1)부터 (3,3)까지 -2의 공격 Skill을 시전한다.
2. (2,0)부터 (4,1)까지 1의 회복 Skill을 시전한다.

빨간 네모는 해당 범위에 -2의 공격을 가하는 Skill이다. 
이 Skill을 누적합 배열에 마킹하면 다음과 같은 모습이다.

위와 같이 마킹해야 누적합 연산을 수행했을 때 원하는 빨간 부분에만 -2의 공격이 수행된다. 
1행을 보면 [ -2, 0, 0, 2]와 같이 되어있는데, 이렇게 두어야 누적합 했을 때  [-2, -2, -2, 0]과 같이 우리가 원하는 모습이 되기 때문이다.
1열도 마찬가지로 [-2, 0, 0, 2]와 같이 두어야 누적합 한 결과가 [-2, -2, -2, 0]으로 원하는 모습이 된다.
 가로로 누적합을 구하고 이어서 세로로 누적합을 구하면 위의 마킹한 배열은 다음과 같이 변한다.

 회복 스킬까지 누적합 배열에 마킹하면, 누적합 배열은 다음과 같은 모습이 된다.

이 상태에서 가로, 세로로 누적합 연산을 수행하면 최종적으로 누적합 배열의 모습은 아래와 같이 변한다.

 

class Solution {
    public int solution(int[][] map, int[][] skills) {
        int answer = 0;

        int height = map.length;
        int width = map[0].length;
        int[][] preSum = new int[height + 1][width + 1];

        for (int i = 0; i < skills.length; i++) {
            int[] skill = skills[i];

            int type = skill[0];
            int x1 = skill[1];
            int y1 = skill[2];
            int x2 = skill[3];
            int y2 = skill[4];
            int degree = skill[5];


            if (type == 1) {
                //공격
                preSum[x1][y1] -= degree;
                preSum[x2 + 1][y2 + 1] -= degree;

                preSum[x1][y2+1] += degree;
                preSum[x2+1][y1] += degree;

            }else{
                //회복
                preSum[x1][y1] += degree;
                preSum[x2 + 1][y2 + 1] += degree;

                preSum[x1][y2+1] -= degree;
                preSum[x2+1][y1] -= degree;
            }
        }

        //가로 방향으로 누적합 배열을 채운다.
        for (int i = 0; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
                preSum[i][j] += preSum[i][j - 1];
            }
        }

        //세로 방향으로 누적합 배열을 채운다.
        for (int i = 1; i <= height; i++) {
            for (int j = 0; j <= width; j++) {
                preSum[i][j] += preSum[i-1][j];
            }
        }

        //기존 map에 누적합 결과를 반영한다.
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] += preSum[i][j];
            }
        }

        //건물 개수 체크
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] > 0) {
                    answer++;
                }
            }
        }
        return answer;
    }
}