프로그래머스 파괴되지 않은 건물 자바 풀이

문제 링크

문제 풀이 시간 : 42분

문제 요약

N x M 크기의 보드(board) 가 있으며, 각 칸에는 건물의 내구도(정수) 가 있음
적과 아군이 번갈아가며 직사각형 영역에 스킬(skill)을 사용함
모든 스킬이 적용된 후, 파괴되지 않은 건물)의 개수를 구해야 함

문제 풀이

이 문제는 보고 2차원 누적합을 사용해야 하나? 라고 생각이 들었다.

하지만 좀 생각해보니 2차원 누적합은 아니고 비슷하게 풀이를 할 수 있는 문제였다.

문제의 예시에서 처럼 5*4의 배열이 있고, 0,0 ~ 3,4에 4의 공격을 한다면,

아래의 사진과 같은 영역에 -4를 해줘야 할 것이다.

하지만 모든 공격, 회복에 대해 이런 작업을 해준다면 당연하게도 시간초과가 난다.

그럼 이걸 어떻게 효율적으로 할 수 있을까??

같은 공격이 있다고 할 때, 우리는 아래와 같이 표시할 수 있다.

이게 무슨 그림이냐?

이 그림은 2차원 차분 기법을 표현한 것이다.

처음에 했던 것과 같이 모든 칸에 값을 더하거나 빼는 대신에 사각형 범위의 네 꼭짓점에서 표시를 해두고 나중에 누적합으로 한번에 계산하는 것이다.

쉽게 설명하자면,

(r1, c1) 위치에는 공격이면 -값, 회복이면 +값을 더해준다.
(r1, c2+1) 에는 그 반대 부호로 값을 빼준다.
(r2+1, c1) 에도 반대 부호로 빼준다.
(r2+1, c2+1) 에는 첫 위치와 같이 다시 더해준다.

이렇게 하면 누적합(가로 → 세로)를 두번 하면 직사각형 전체 영역이 자동으로 채워지게 된다.

즉, 직사각형 범위에 동일한 값을 더하거나 뺀다는 연산을 $O(1)$ 에 표시하고, 나중에 누적합으로 $O(N*M)$ 에 한번에 처리하는 것이다.

최종 코드

java

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer;
        int r = board.length;
        int c = board[0].length;
        answer = r*c;
        int[][] diff = new int[r+1][c+1];
        
        for(int[] now : skill){
            int r1 = now[1];
            int r2 = now[3];
            int c1 = now[2];
            int c2 = now[4];
            //공격이면 음수, 회복이면 양수
            int num = now[0] == 1 ? now[5]*-1 : now[5];
            
            //네 꼭짓점 업데이트
            diff[r1][c1] += num;
            diff[r1][c2+1] -= num;
            diff[r2+1][c1] -= num;
            diff[r2+1][c2+1] += num;
        }
        
        //가로 방향 누적합
        for(int i=0;i<r+1;i++){
            for(int j=1;j<c+1;j++){
                diff[i][j] += diff[i][j-1];
            }
        }
        
        //세로 방향 누적합
        for(int j=0;j<c+1;j++){
            for(int i=1;i<r+1;i++)
                diff[i][j] += diff[i-1][j];
        }
        
        //최종 건물 내구도 구하기
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                board[i][j] += diff[i][j];
                //내구도가 0 이하면 파괴된 건물
                if(board[i][j]<=0)
                    answer--;
            }
        }
        
        return answer;
    }
}

파괴되지 않은 건물

문제 풀이 시간 : 42분

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기