Programmers - 파괴되지 않은 건물 with JAVA (V)

 

문제

2차원 배열이 주어진다. 그리고 각 스킬들이 주어지는데 스킬은 공격, 회복 두 개로 나뉜다. 공격시에는 해당 범위만큼 2차원배열에서 특정 값을 빼고 회복시에는 해당 범위만큼 2차원 배열에서 특정 값을 더 해준다. 결과적으로 배열에서 1보다 큰 칸의 개수를 구하라.

 

 

 

 

로직

첫번째로 굉장히 쉬워보이는 문제지만 요구사항을 확인해보면 배열 한 행과 열의 크기는 최대 1000, skill의 개수는 최대 25000이다. 따라서 25000 * 1000 * 1000, O(KNM)의 시간복잡도로는 효율성 테스트를 통과할 수 없다.

(스킬 수 K, 맵의 가로 N, 맵의 세로 M)

 

누적합을 통해 해결하고자 한다.

로직은 우선 아래와 같다.

 

1. 스킬마다 누적합을 위한 값을 구한다. O(K)

2. 구한 누적합으로 최종 누적합을 구한다. O(NM)

3. board에서 누적 결과 값을 더해 최종 결과가 1이상인 칸의 수를 구한다. O(NM)

=> O(K + NM)

 

누적합을 구하는 원리는 아래와 같다.

예를 들어, 문제에서 보드의 (0, 0)에서 (3, 3)까지 3을 더하려고 한다고 가정한다. 이 때 해당 스킬의 누적합은 아래와 같다.

[3, 0, 0, -3]

[0, 0, 0, 0]

[0, 0, 0, 0]

[-3, 0, 0, 3]

 

이제 Map이 0으로 초기화되었다고 가정하면

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

 

-> (0, 0)끼리 더한다. 현재 누적된 값은 3이다.(누적합 맵의 0, 0)

[3, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

 

-> (0, 1)애 누적된 값을 더한다. (누적합 맵의 (0, 0) + (0, 1))

[3, 3, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

 

-> (0, 1)애 누적된 값을 더한다. (누적합 맵의 (0, 0) + (0, 1) + (0, 2))

[3, 3, 3, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

 

-> (0, 1)애 누적된 값을 더한다, 누적된 값은 3 + -3 즉 0이다. (누적합 맵의 (0, 0) + (0, 1) + (0, 2) + (0,3))

[3, 3, 3, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

 

 

이런방식으로 누적합을 구하고 결론적으로 모든 스킬의 누적합을 구하고 누적합 결과를 도출해 board에 한번에 더해주는 방식이다.

따라서 시간복잡도가 많이 줄어드게 되는 것이다.

 

 

코드

 

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;       
        int[][] map = new int[board.length+1][board[0].length+1];
        // 누적합
        for(int[] now : skill){
            if(now[0] == 1){
                map[now[1]][now[2]] -= now[5];
                map[now[1]][now[4]+1] += now[5];
                map[now[3]+1][now[4]+1] -= now[5];
                map[now[3]+1][now[2]] += now[5];
            }
            else{
                map[now[1]][now[2]] += now[5];
                map[now[1]][now[4]+1] -= now[5];
                map[now[3]+1][now[4]+1] += now[5];
                map[now[3]+1][now[2]] -= now[5];
            }
        }
        // 결과 도출
        for(int i=0; i<map.length; i++){
            int now = map[i][0];
            for(int j=1; j<map[0].length; j++){
                map[i][j] += now;
                now = map[i][j];
            }
        }
        for(int i=0; i<map[0].length; i++){
            int now = map[0][i];
            for(int j=1; j<map.length; j++){
                map[j][i] += now;
                now = map[j][i];
            }
        }
        // 결과
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] + map[i][j] > 0){
                    answer += 1;
                }
            }
        }
        return answer;
    }
}

 

 

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int n = board.length;
        int m = board[0].length;
        int[][] sum = new int[n+1][m+1];
        for(int[] now : skill){
            if(now[0] == 1){
                sum[now[1]][now[2]] -= now[5];
                sum[now[1]][now[4]+1] += now[5];
                sum[now[3]+1][now[2]] += now[5];
                sum[now[3]+1][now[4]+1] -= now[5];
            }
            else{
                sum[now[1]][now[2]] += now[5];
                sum[now[1]][now[4]+1] -= now[5];
                sum[now[3]+1][now[2]] -= now[5];
                sum[now[3]+1][now[4]+1] += now[5];
            }
        }
        for(int x=0; x<n+1; x++){
            for(int y=1; y<m+1; y++){
                sum[x][y] += sum[x][y-1];
            }
        }
        for(int y=0; y<m+1; y++){
            for(int x=1; x<n+1; x++){
                sum[x][y] += sum[x-1][y];
            }
        }
        for(int x=0; x<n; x++){
            for(int y=0; y<m; y++){
                if(board[x][y] + sum[x][y] > 0){
                    answer += 1;
                }
            }
        }
        return answer;
    }
}