프로그래머스 - 파괴되지 않은 건물(Java)

누적합 문제입니다.

자세한 설명은 https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/에 있으니 꼭 읽어보시기 바랍니다.

이 문제는 해결 방법만 알면 구현하기 매우 간단한 문제입니다.(물론, 해결 방법을 알아내기 쉽지 않습니다.)

 

행의 길이를 N, 열의 길이를 M, 스킬의 길이를 K라고 하면 대충 단순한 반복문을 통한 해결 방법의 시간 복잡도는 O(NMK)가 됩니다.

시간 복잡도에 따라 대략 250,000,000,000정도가 걸리니 효율성을 통과하지 못합니다.

단순한 반복문으로도 정확성을 아주 간단하게 통과할 수 있지만, 입력의 범위가 매우 크므로 누적합을 사용해야만 합니다.

 

문제 해결의 접근 방식은 아주 간단합니다.

(x1, y1)에서 부터 (x2, y2)까지의 값을 더하거나 빼야 하므로, 별도의 배열을 선언하여 시작과 끝+1 위치에만 스킬의 공격 및 회복을 더해주면 됩니다.

스킬의 공격 및 회복의 값을 n이라고 하고, (0,0)~(3,3)까지 회복을 하면 다음 그림과 같이 나타나게 됩니다.

이제 가로 먼저 누적합을 해 보겠습니다.

누적합은 이전의 값을 더하면 됩니다.(빈 칸의 값은 0 이지만, 가시성을 위해 그림에서 제거했습니다.)

즉, 그림과 같이 나타납니다.

첫 번째 그림과 두 번째 그림의 0행과 4행을 비교해 보세요.

가로의 누적합이 끝나면 세로의 누적합을 하면 됩니다.

그러면 다음 그림과 같이 나타납니다.

이제 이해 되셨나요?

단 두 번만의 반복으로 스킬의 영향을 받는 위치를 쉽게 알 수 있습니다.

 

※주의※

그림에서 4번부터 0까지 타고 가는것 처럼 보이지만, 

실제 코딩으로 구현 할 때 4열,행이 아닌 1열,행부터 시작하셔야 합니다.

 

다시 돌아와서, (x1, y1)부터 (x2, y2)까지 영향을 받도록 하는 누적합의 좌표값은 어떻게 셋팅하면 될까요?

네, 아래 네 개와 같습니다.

1. damages[x1][y1] += n
2. damages[x1][y2 + 1] -= n
3. damages[x2+1][y1] -= n
4. damages[x2 + 1][y2 + 1] += n

[구현 코드]

class Solution {
    private static int type, r1, c1, r2, c2, degree;

    public int solution(int[][] board, int[][] skill) {
        int[][] damages = new int[board.length + 1][board[0].length + 1];

        for (int i = 0; i < skill.length; i++) {
            type = skill[i][0];
            r1 = skill[i][1];
            c1 = skill[i][2];
            r2 = skill[i][3];
            c2 = skill[i][4];
            degree = skill[i][5];

            // 공격이면
            if (type == 1) degree = degree * (-1);

            damages[r1][c1] += degree;
            damages[r1][c2 + 1] -= degree;
            damages[r2 + 1][c1] -= degree;
            damages[r2 + 1][c2 + 1] += degree;
        }

       // 열 누적합
        for (int i = 0; i < damages.length; i++) {
            for (int j = 1; j < damages[i].length; j++) {
                damages[i][j] += damages[i][j - 1];
            }
        }

        // 행 누적합
        for (int i = 1; i < damages.length; i++) {
            for (int j = 0; j < damages[i].length; j++) {
                damages[i][j] += damages[i - 1][j];
            }
        }

        int cnt = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] + damages[i][j] > 0) cnt++;
            }
        }

        return cnt;
    }
}