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

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

프로그래머스

코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 파괴되지 않은 건물

 

난이도: LEVEL3

알고리즘 유형: 누적합 

시간 초과 코드 

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        
        for(int i = 0; i < skill.length; i++){
            int type = skill[i][0];
            int degree = skill[i][5];
            for(int j = skill[i][1]; j <= skill[i][3]; j++){
                for(int k = skill[i][2]; k <= skill[i][4]; k++){
                    if(type == 1){
                        board[j][k] -= degree;
                    }
                    else{
                        board[j][k] += degree;
                    }
                }
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] >= 1) answer++;
            }
        }
        return answer;
    }
}

 

skill이 최대 25만 board 배열의 크기가 최대 1000 * 1000 

해당 풀이는 최악의 경우 250000 * 1000 * 1000 시간 복잡도가 나온다.

정확성 테스트는 skill 크기도 작고 배열 크기도 최대 100 * 100 이어서 통과하지만

효율성 테스트 전부를 틀린다. 

정답 코드 핵심 아이디어 

특정 구간 (a, b) ~ (c, d)에 변화를 준다고 하면 

x 구간은 a ~ c  y 구간은 b ~ d 

모든 스킬에 대해서 바로바로 board에 적용하면 시간 복잡도 때문에 통과하지 못한다. 

 

그래서 구간의 변화량을 기록하는 배열을 만들고 해당 배열에 skill에서의 변화를 기록한다. 

 

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

 

해당 배열은 4 * 5 크기의 변화량을 기록하는 배열이다. 

 

구간 (0,0) ~ (2,2) 까지 type = 2 (회복) degree = 2 라고 할 때 

우리가 원하는 변화는 아래와 같다. 

 

2 2 2 0 0

2 2 2 0 0

2 2 2 0 0

0 0 0 0 0

 

전체를 기록하는 게 아닌 4가지 포인트에 이와 같은 변화량을 기록할 수 있다. 

 

2 0 0 -2 0

0 0 0 0 0

0 0 0 0 0

-2 0 0 2 0

 

1. 열에 대한 누적합 

 

2 2 2 0 0

0 0 0 0 0

0 0 0 0 0

-2 -2 -2 0 0

 

2. 행에 대한 누적합 

 

2 2 2 0 0

2 2 2 0 0 

2 2 2 0 0 

0 0 0 0 0 

 

우리가 원했던 배열이 나왔다. 

정답 코드 

import java.util.*;
class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        
        int n = board.length;
        int m = board[0].length;
        
        // 변화량을 기록하는 memo 배열 
        int [][] memo = new int [n + 1][m + 1];
        for(int i = 0; i < skill.length; i++){
            int degree = skill[i][5];
            int type = skill[i][0];
            int a = skill[i][1];
            int b = skill[i][2];
            int c = skill[i][3];
            int d = skill[i][4];
            if(type == 1){ // 공격
                memo[a][b] -= degree;
                memo[a][d+1] += degree;
                memo[c+1][b] += degree;
                memo[c+1][d+1] -= degree;
            }
            else{ // 회복 
                memo[a][b] += degree;
                memo[a][d+1] -= degree;
                memo[c+1][b] -= degree;
                memo[c+1][d+1] += degree;
            }
        }
        
        // 변화량 누적합 구하기 왼 -> 오른 
        for(int i = 0; i < n + 1; i++){
            for(int j = 0; j < m + 1; j++){
                if(j == 0) continue;
                memo[i][j] += memo[i][j-1];
            }
        }
        // 변화량 누적합 구하기 위 -> 아래
        for(int i = 0; i < n + 1; i++){
            if(i == 0) continue;
            for(int j = 0; j < m + 1; j++){
                memo[i][j] += memo[i-1][j];
            }
        }
        
        // 변화량 적용하기, 정답 구하기 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                board[i][j] += memo[i][j];
                if(board[i][j] >= 1) answer++;
            }
        }
        
        return answer;
    }
}

 

 

내가 참고해서 푼 풀이 - 프로그래머스 파괴되지 않은 건물 질문 게시판 

https://school.programmers.co.kr/questions/25471

프로그래머스