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

[문제링크]

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

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

---

[설명]

이 문제는 완전탐색으로 풀었는데 효율성에서 통과하지 못하였습니다.

찾아보니 다른분들께서 누적합으로 풀은 것을 볼 수 있습니다.

 

누적 합으로 푸는 방법

1) sum이라는 배열을 만든다.(board의 세로 길이가 M, 가로 길이가 N일 때, sum = new int[M+1][N+1] 로 선언을 해야한다. 그 이유는 누적합을 할 때, 끝점에서 +1한 점도 누적합에 포함해야 하기 때문이다.)

2) 좌->우로 누적합을 적용합니다.

3) 상->하로 누적합을 적용합니다.

4) 원래 값인 board에 sum배열을 합친 것이 0보다 클 경우 answer를 ++해준다.

 

 

프로그래머스 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물 JAVA풀이

 

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int M=board.length, N=board[0].length;
        int[][] sum = new int[M+1][N+1];
        //누적합 좌표
        for(int[] s : skill){
            int i1=s[1], j1=s[2];
            int i2=s[3], j2=s[4];
            int d=s[5]*(s[0]==1?-1:1);
            sum[i1][j1]+=d;
            sum[i2+1][j1]+=d*-1;
            sum[i1][j2+1]+=d*-1;
            sum[i2+1][j2+1]+=d;
        }
        // 좌 -> 우
        for(int j=1;j<N;j++){
            for(int i=0;i<M;i++){
                sum[i][j]+=sum[i][j-1];
            }
        }
        // 상 -> 하
        for(int i=1;i<M;i++){
            for(int j=0;j<N;j++){
                sum[i][j]+=sum[i-1][j];
            }
        }
        // 누적합
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(board[i][j]+sum[i][j]>0)answer++;
            }
        }
        
        return answer;
    }
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.