Kakao 2022 Blind Test - Lv3. 파괴되지 않은 건물 (Java)

문제 요약

범위와 degree가 주어지면 type에 따라 건물이 파괴되거나 회복된다. 최종적으로 건물의 내구도를 파악하여 파괴되지 않은 건물의 수를 반환하라. 

 

[문제 설명] 

• N x M 크기의 행렬 모양 맵이 있다.
• 내구도를 가진 건물이 각 칸마다 존재한다. 
• type이 1이면 degree 만큼 건물의 내구도가 감소하고, type이 2이면 degree 만큼 건물의 내구도가 회복한다.
• 최종적으로 건물의 내구도가 0이하이면 건물은 파괴된다.
  • 중간에 건물의 내구도가 0이하일지라도 공격을 받으면 내구도는 계속 감소한다.
  • 즉, 최종 값을 근거로 건물은 파괴된다. 

 

[제한 사항]

1. board(N x M): 건물의 맵(행과 열) (1 ≤ 건물의 행(N) or 건물의 열(M) ≤ 1,000, 1 ≤ 건물의 내구도 ≤ 1,000) 
2. skill: type, 범위, 공격 or 회복 크기(degree) (1 ≤ skill 배열 크기 ≤ 250,000, 1 ≤ degree ≤ 500) 

board	skill	result
[[1,2,3],[4,5,6],[7,8,9]]	[[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]	6

 

---

문제 접근 

• imos 알고리즘 사용 (위 입출력예를 가지고 설명)
  • 누적합 이용 

 

// 22. 06. 29. 수 - 파괴되지 않은 건물 - imos algorithm

public class Solution {
    public static void main(String[] args) {
        System.out.println(solution(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
                , new int[][]{{1, 1, 1, 2, 2, 4}, {1, 0, 0, 1, 1, 2}, {2, 2, 0, 2, 0, 100}}));
    }

    public static int solution(int[][] board, int[][] skill) {
        int answer = 0;

        int N = board.length;
        int M = board[0].length;

        // 1. 누적합을 보관할 배열 만들기
        int[][] cumulative_map = new int[N+1][M+1];

        // 2. skill 배열 값을 읽으며 누적합 계산을 위해 범위의 시작과 끝에 degree 값 세팅하기
        for(int i = 0, length = skill.length; i < length; i++) {
            int type = skill[i][0];
            int r1 = skill[i][1];
            int c1 = skill[i][2];
            int r2 = skill[i][3];
            int c2 = skill[i][4];
            int degree = type == 1 ? skill[i][5] * -1 : skill[i][5];

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

        // 2. 세팅된 degree 값 이용하여 누적합 해주기 - 행
        for(int r = 0; r <= N; r++) {
            int prior = cumulative_map[r][0];
            for(int c = 1; c <= M; c++) {
                cumulative_map[r][c] += prior;
                prior = cumulative_map[r][c];
            }
        }

        // 열
        for(int c = 0; c <= M; c++) {
            int prior = cumulative_map[0][c];
            for(int r = 1; r <= N; r++) {
                cumulative_map[r][c] += prior;
                prior = cumulative_map[r][c];
            }
        }

        // 원래 배열과 더해주기
        for(int r = 0; r < N; r++) {
            for(int c = 0; c < M; c++) {
                board[r][c] += cumulative_map[r][c];
                if(board[r][c] > 0) answer++;
            }
        }

        return answer;
    }
}

---

느낀점

'파괴되지 않은 건물'의 경우 2차원 배열을 일일이 방문하여 건물의 내구도를 더하고 빼준다면 분명 시간초과가 날 것이 분명했기에 다른 방법을 선택해야 했다. 공부한 결과 imos 알고리즘을 이용하여 해결하는 문제였다. imos 알고리즘은 누적합의 개념을 활용한 개념이다. 기존에 알고있던 누적합이란, 1차원 배열이 있을 때 배열의 전체 합을 더한 것에서 구하고자 하는 범위를 제외한 칸의 합을 더한 값을 빼주는 방식이었다. 반면, imos 알고리즘은 배열의 범위가 주어졌을 때, 매 번 누적합을 해주는 것이 아니라 4칸에 누적할 값을 더하거나 빼주어 마지막에 전체적으로 누적합을 구하는 방식인 것이다. 덕분에 O(N * M * skill의 개수)에서 O(N * M + skill)로 시간복잡도를 나눠주어 효율성 검증을 통과할 수 있었다. 꼭 기억하여 다음 번에도 활용할 수 있도록 하자. 

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/92344

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