[프로그래머스] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT)-JAVA

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

코딩테스트 연습 - 파괴되지 않은 건물

[문제 설명]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

 

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

 

[제한 사항]

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

[풀이]

결론부터 말하자면 해당 문제는 '누적합' 이라는 것을 통해 해결해야 하는 알고리즘 문제이다. 필자도 스스로 해결하지 못해 타 블로그들을 참고하여 해결하였다.

 

먼저 board 2차원 배열보다 행과 열이 한개씩 많은 result 라는 2차원 배열을 새롭게 생성한다. 그냥 바로 완전탐색을 통해 문제를 해결하고자 하면 효율성 테스트에서 걸리게 된다. 따라서 누적합을 활용해야 문제를 해결할 수 있다. 

 

이후 skill 배열의 각 행을 for문으로 돌면서 다음 코드처럼 실행한다. 

        int[][] result = new int[n + 1][m + 1];

        for (int[]price : skill) {
            int type = price[0];
            int num = type == 1 ? -price[5] : price[5];
            int s1 = price[1];
            int e1 = price[2];
            int s2 = price[3];
            int e2 = price[4];

            result[s1][e1] += num;
            result[s1][e2 + 1] += -num;
            result[s2+1][e1] += -num;
            result[s2 + 1][e2 + 1] += num;
        }

위 코드의 마지막 4줄이 누적합을 위한 준비 단계이다. 차후 위에서 아래로 한번, 좌에서 우로 한번해서 총 2번 누적합을 구할 것이기 떄문에 위와 같이 설정하였다.

 

최종 코드는 다음과 같다. 

public class UndestroyedBuilding {

    public static void main(String[] args) {
        int[][] board = {{5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}};
        int[][] skill = {{1, 0, 0, 3, 4, 4}, {1, 2, 0, 2, 3, 2}, {2, 1, 0, 3, 1, 2}, {1, 0, 1, 3, 3, 1}};

        int n = board.length;
        int m = board[0].length;

        int[][] result = new int[n + 1][m + 1];

        for (int[]price : skill) {
            int type = price[0];
            int num = type == 1 ? -price[5] : price[5];
            int s1 = price[1];
            int e1 = price[2];
            int s2 = price[3];
            int e2 = price[4];

            result[s1][e1] += num;
            result[s1][e2 + 1] += -num;
            result[s2+1][e1] += -num;
            result[s2 + 1][e2 + 1] += num;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] += result[i - 1][j];
            }
        }
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                result[i][j] += result[i][j-1];
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(board[i][j]+result[i][j]>0) answer++;
            }
        }
        System.out.println(answer);
    }
}