프로그래머스 파괴되지 않은 건물 92344 Java (level 3)

2022 KAKAO BLIND RECRUITMENT

 

문제자체는 굉장히 단순해 이해하기 쉽다. 

헷갈리는 부분은 파괴된 건물이 다시 회복을 할 수 있다 정도이다.

 

문제 요약

NxM Map에 건물이 각 칸마다 존재, 내구도 0이하 시 파괴 

skill의 Type 에 따라 (r1,c1) - (r2,c2) 직사각형 범위에 degree 만큼 공격 혹은 회복 

 

• 입력:
  • 건물 내구도 2차원 정수 배열 board(n,m <=100) , 회복 스킬 2차원 정수 배열 skill (<= 250000)
• 출력:
  • 최종적으로 파괴되지 않은 건물 개수를 return한다

접근 방식

m,n 이 각 100 이하 skill 행 개수가  250000 이하이므로 최악의 시간복잡도를 따져보면

100*100*250000 이면 25억이되면서 시간초과가 발생할 수 있다.

이때 매번 직사각형 범위에 degree만큼 값을 빼주고 더해주는 것이 굉장히 비효율적이고 한번에 처리하면 좋을 것 같았는데

솔직히 방법이 떠오르지 않았다. 

구글링을 통해 2차원 누적합에 대해 이해했고 이어서 설명하도록 하겠다 :)

이때 board값에 diff라는 2차원 배열을 만들어서 degree값들을 누적합을 통해서 기록하는 방법이다. 

핑크색 직사각형 범위에 (r1,c1)~ (r2,c2) 

n 만큼 공격을 해야한다고 가정하자 

 

그리고 2차원이다보니 열 , 행 별로 누적합을 진행할 것인데 

열로 합치는 방향은 →

행으로 합치는 방향은 ↓

이라고 가정하자 

 

코드로 보면

diff[r1][c1]+= n

 

여기서 열로 누적합을 하게 되면

열로 합치는 방향은 → 이니까

 

↓ㅇ

인데 (r1, c2+1) 은 공격을 받는 범위가 아니어서 n 이 있으면 안된다 

따라서 코드는 다음과 같이 계산이 된다. 

diff[r1][c2+1] -= n;

↓

초기값은 다음 과 같고

열으로 누적합을 하고나서, 행으로 누적합을 진행하게 되고 나면 다음과 같다.

여기서 마지막줄은 n일 이유가 없다. 

따라서 초기값에 (r2+1, c1) 에도 -n 이 있어야한다.

diff[r2+1][c1] -= dtmp;

이렇게 되어있다고 생각했을 때 핑크색 직사각형에만 n이 채워질수 있는지 확인해보자. 

그러면 열로 누적합을 진행하면 다음과 같다.

그리고 행으로 누적합을 하게 된다면 

다음과 같다.

(r2+1, c2+1) 에서 -n 이 여전히 남는 것을 알 수 있다.

 

그래서 초기값 설정을 다음과 같이 해야한다.

diff[r1][c1] += n;
diff[r1][c2+1] -= n;
diff[r2+1][c1] -= n;
diff[r2+1][c2+1] += n; // 추가된 부분

이와 같이 해야한다.

그리고나서 열과 행을 누적합하게 되면,

이렇게 원하는 범위에 n이 채워지는 연산을 시간복잡도가 (r2-r1)*(c2c-1 ) ( 최대 99*99) 인데 

O(1) 에 할 수 있다. 

 

그렇게 정리된 diff배열을 내구도배열인 board 배열에 더하고, 내구도가 1미만 (0이하) 인것을 count하여 return하면 된다.

 

해결한 풀이는 다음과 같다.

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int m = board.length;
        int n= board[0].length;
        
        // 여기서 1을 추가해서 배열을 만드는 이유는 
        // diff[r2+1][c2+1] +=dtmp; 누적합 시 범위를 초과할 수 있기 때문
        int[][] diff = new int[m+1][n+1];
        int answer = 0;
        int s = skill.length;
        for(int i =0;i<s;i++){
            int dtmp = skill[i][5];
            if( skill[i][0]==1){
                dtmp*=-1;
            } 
            int r1 = skill[i][1];
            int c1= skill[i][2];
            int r2 =skill[i][3];
            int c2 =skill[i][4];
            
            diff[r1][c1]+= dtmp;
            diff[r1][c2+1] -= dtmp;
            diff[r2+1][c1] -= dtmp;
            diff[r2+1][c2+1] +=dtmp;
        }
        // 열
        for (int i =0;i<m;i++){
            for(int j =1;j<n;j++){
                diff[i][j] += diff[i][j-1];
            }
        }
        // 행 
        for (int i =0;i<n;i++ ){
            for(int j =1;j<m;j++){
                diff[j][i] += diff[j-1][i]; 
            }
        }
        
        for(int i =0;i<m;i++){
            for(int j =0;j<n;j++){
                board[i][j] +=diff[i][j];
                if(board[i][j]>=1){
                    answer++;
                }
            }
        }
        
        return answer;
    }
  
}

 

Eug2n2's GitHub