[프로그래머스/Level3] 파괴되지 않은 건물 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 누적합 (시간 복잡도 : O(N+M) = O(N))

필요 자료구조
- 모든 skills에 대한 처리를 저장할 누적합 2차원 배열 💥

 

1. 반복문으로 스킬 배열을 돌며 새로 생성한 누적합 배열에 degree를 배치한다.

2. 가로 누적합과 세로 누적합을 구한다.

3. 건물 배열과 누적합 배열의 값을 더한 값이 0보다 크다면 붕괴되지 않은 건물이므로 정답 +1한다.

 

 

 

💥 유의사항

- O(N * M * K)했다간 시간 초과가 발생한다. 그래서 누적합으로 해결

- N+1, M+1까지 계산 가능해야 하므로 기존 board 배열의 크기보다 행과 열 크기를 1씩 크게 잡아줘야 한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[][] board, skill, sum;
    static int N, M;    
    
    public int solution(int[][] board, int[][] skill) {
        this.board = board;
        this.skill = skill;
        
        N = board.length;
        M = board[0].length;
        sum = new int[N+1][M+1];
        
        for(int[] s : skill) {
            int type = s[0];
            int r1 = s[1]; int c1 = s[2];
            int r2 = s[3]; int c2 = s[4];
            int degree = s[5];
            
            if(type == 1) { // 적군
                sum[r1][c1] -= degree;
                sum[r1][c2 + 1] += degree;
                sum[r2 + 1][c1] += degree;
                sum[r2 + 1][c2 + 1] -= degree;
            }
            else {  // 아군
                sum[r1][c1] += degree;
                sum[r1][c2 + 1] -= degree;
                sum[r2 + 1][c1] -= degree;
                sum[r2 + 1][c2 + 1] += degree;
            }
        }        
        
        calc();
        
        // 파괴되지 않은 건물 찾기
        int answer = 0;         
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(sum[i][j] + board[i][j] > 0)
                    answer++;
            }
        }
        
        return answer;
    }
    
    // 누적합 계산 메서드
    private static void calc() {
        // 가로 누적합 구하기 (왼쪽 → 오른쪽)
        for(int i = 0 ; i <= N ; i++) {
            for(int j = 0 ; j < M ; j++)
                sum[i][j + 1] += sum[i][j];
        }
        
        // 세로 누적합 구하기 (위 → 아래)
        for(int i = 0 ; i <= M ; i++) {
            for(int j = 0 ; j < N ; j++)
                sum[j + 1][i] += sum[j][i];
        }
    }
}

 

 

---

💦 어려웠던 점

- 브루트포스로 풀었더니 효율성은 모두 틀렸다...😅

틀린 코드 확인하기

import java.util.*;
 
class Solution {
    static int[][] board, skill;
    static int N, M;    
    
    public int solution(int[][] board, int[][] skill) {
        this.board = board;
        this.skill = skill;
        
        N = board.length;
        M = board[0].length;
 
        for(int i = 0 ; i < skill.length ; i++) {   // 25만 * 1만 = 25 * 10^8 => 시간 초과
            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 = skill[i][5];
            
            if(type == 1) { // 적군
                for(int a = r1 ; a <= r2 ; a++) {
                    for(int b = c1 ; b <= c2 ; b++) {
                        board[a][b] -= degree;
                    }
                }
            }
            else {  // 아군
                for(int a = r1 ; a <= r2 ; a++) {
                    for(int b = c1 ; b <= c2 ; b++) {
                        board[a][b] += degree;
                    }
                }
            }
        }        
        
        int answer = 0; // 파괴되지 않은 건물 수
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(board[i][j] > 0)
                    answer++;
            }
        }
        
        return answer;
    }
}

 

 

 

- 그럼 혹시 누적합..? 했는데 누적합 문제였다고 한다.. (누적합인 거 알아채고도 풀이는 쉽게 생각이 나지 않았음)

 

 

🧐 새로 알게 된 내용

- 2차원 누적합 구하는 방법

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 누적합 관련 최고의 설명!!!!!

왜 좌우 n, -n 이렇게 진행되는지 몰랐는데 여기서 잘 정리해주신 덕에 이해할 수 있었다..

[Java/C++] 프로그래머스 Level 3 - 파괴되지 않는 건물

 

 

 

✔ 친절한 그림 설명...

[프로그래머스] 파괴되지 않은 건물

2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물 (JAVA)