[프로그래머스] 2022 카카오 블라인드 파괴되지 않은 건물 - JAVA

LeeJaeHoon·2022년 9월 21일
0

문제

파괴되지 않는 건물
건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

풀이

정확성 테스트 케이스는 board의 행과 열의 길이제한이 100,
skill의 길이 제한이 100이므로 브루트포스를 이용하여 답을 구할 수 있다.
이때의 시간복잡도는 O(N x M x K)가 되게된다.
하지만 해당 풀이는 효율성 테스트에서는 시간초과가 발생한다.
효율성 테스트에서는 250,000 x 1000 x 1000 이므로 시간초과가 발생하게 된다.

그러면 어떻게 시간 복잡도를 줄일 수 있을까?
바로 누적합을 이용하면 된다. [0,0,0,0,0] 배열이 있을때 0~3번까지 -2를 해줘야한다면 어떻게 해야할까?
반복문을 돌면서 0~3까지 -2를 해주는 방법이 있을것이다. 하지만 이 방법은 앞에서 말했다 싶이 시간초과가 난다.
두번째 방법으로 해당 배열의 크기만큼 새로운 배열을 만들고 다음과 같이 채워넣으면 된다. [-2,0,0,0,2]
이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되게 된다. 이렇게 구한 누적합과 board의 값을 합해줘 답을 구해주면 된다.

이 방식으로 문제를 풀면 O(NMK)의 복잡도를 O(NK)로 줄일 수 있지만, 이 또한 시간 초과가 발생한다.
O(K)로 줄일 수 없을까?? 위의 아이디어를 2차원 배열로 확장해 생각해 보자.
2차원 배열에서 (0,0)부터 (2,2) 까지 n만큼 변화 시키는 경우를 예로 들어보겠다.

해당 배열의 행 부분만 봐서 위의 아이디어를 적용시키면 다음과 같다.

n 0 0 -n
n 0 0 -n
n 0 0 -n

위 행렬을 다시 열만 따로 보면 가장 왼쪽의 열은 n만큼의 변화가, 가장 오른쪽 열은 -n만큼의 변화가 일어난 것을 알 수 있다. 즉 각 열에 대해서도 위의 아이디어를 적용시킬 수 있다.

n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n

즉, 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는 (x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같게 된다.
이런식으로 배열을 구해준 후 해당 배열을 위에서 아래로 누적합을 구한 뒤, 왼쪽에서 오른쪽으로 누적합하거나 왼쪽에서 오른쪽으로 누적합 을 해주고 board와 해당 누적합을 더해줘 정답을 구할 수 있다.

코드

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][M];
        for(int i=0; i<skill.length; i++) {
            int r1 = skill[i][1];
            int c1 = skill[i][2];
            int r2 = skill[i][3];
            int c2 = skill[i][4];
            int degree = skill[i][5];
            if(skill[i][0] == 1) degree = degree * -1;
            sum[r1][c1] += degree;
            if(r2 + 1 < N) sum[r2+1][c1] -= degree;
            if(c2 + 1 < M) sum[r1][c2+1] -= degree;
            if(c2 + 1 < M && r2 + 1 < N) sum[r2+1][c2+1] += degree;
        }
        
        for(int i=0; i<N-1; i++) {
            for(int j=0; j<M; j++) {
                sum[i+1][j] += sum[i][j];
            }   
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M-1; j++) {
                sum[i][j+1] += sum[i][j];
            }   
        }
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                board[i][j] += sum[i][j];
                if(board[i][j] > 0 ) answer++;
            }   
        }
        return answer;
    }
}

0개의 댓글