Lv 3. 파괴되지 않은 건물

 

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=java

프로그래머스

 

 

 

이 문제를 접하고 우선 구현가능한지 시간복잡도 계산을 해보았고 

최대 1000*1000 배열에 1000*1000 size의 skill 25만개 기준 2500억

즉 시간초과로 불가능할것 같아 

여러 방면으로 고민하고 문제 풀이방법을 찾아보았지만 찾을 수 없었다.

 

그러던 와중 아래의 블로그를 참고하여 풀이방법을 알아낼 수 있었고

아래의 블로그에서 제시한 '누적합' 알고리즘을 활용하여 쉽게 풀이할 수 있었다.

 

'누적합' 알고리즘을 생각하지 못한것은 아니지만 활용을 2차원 array 에서

할수 있을것이라고 상상하지 못했던 것이 큰것 같다.

 

우선 1,3 3,5 좌표와 degree, type이 들어오면 

type 이 1이면 공격 즉 (-)  2면 힐 즉(+) 가된다.

1,3 좌표와 3,5 좌표 에서는 +degree

1,5, 3,3 좌표에서는 -degree를 하여 sum[][] 을 생성하고

기입을 한다면 누적합 알고리즘을 통해서 

 쉽게 풀이가 가능하다.

 

누적합 알고리즘은 아래 참고하였던 블로그 주소를 참고하자.

상당히 친절한 설명으로 잘 이해할 수 있었다.

 

 

https://howudong.tistory.com/418

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

 

import java.util.*;
import java.io.*;

class Solution {
    int[][] sum;
    int sizeX,sizeY;
    int calculate(int[][] board, int x, int y){
        int answer = 0;
        for(int i = 0 ; i < x ; i++){
            for(int j = 0 ; j < y ; j++){
                if(board[i][j]+sum[i][j] > 0)
                    answer++;
            }
        }
        return answer;
    }
    void prefixSum(int[][] board){
        for(int i = 0 ; i < sum.length-1 ; i++){
            for(int j = 0 ; j < sum[0].length-1 ; j++){
                sum[i][j+1] = sum[i][j+1]+sum[i][j];
            }
        }
        for(int j = 0 ; j < sum[0].length-1 ; j++){
            for(int i = 0 ; i < sum.length-1 ; i++){
                sum[i+1][j] = sum[i+1][j]+sum[i][j];
            }
        }

    }
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        sizeX = board.length;
        sizeY = board[0].length;
        sum = new int[sizeX+1][sizeY+1];
        for(int i = 0 ; i < sizeX+1 ; i++){
            Arrays.fill(sum[i],0);
        }
        for(int[] skillSet : skill){
            int type = (skillSet[0] == 1) ? -1 : 1;
            int degree = skillSet[5];
            int r1 = skillSet[1];
            int c1 = skillSet[2];
            int r2 = skillSet[3];
            int c2 = skillSet[4];
            sum[r1][c1] += degree*type;
            sum[r2+1][c2+1] += degree*type;
            sum[r1][c2+1] += -degree*type;
            sum[r2+1][c1] += -degree*type;
        }

        prefixSum(board);
        return calculate(board,sizeX,sizeY);
    }
}