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

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 파괴되지 않은 건물 자바 풀이를 작성하고자 합니다.

 

문제 출처:  https://school.programmers.co.kr/learn/courses/30/lessons/92344#

프로그래머스

 

 

 

1. 풀이 소스

 

class Solution {
    public int solution(int[][] board, int[][] skills) {
        int n = board.length; 
        int m = board[0].length;

        int[][] sum = new int[n + 1][m + 1];
        for (int[] skill : skills) {
            int r1 = skill[1], c1 = skill[2];
            int r2 = skill[3], c2 = skill[4];

            int degree = skill[5] * (skill[0] == 1 ? -1 : 1); // type == 1 이라면 degree 음수, type == 2라면 degree 양수

            sum[r1][c1] += degree;
            sum[r1][c2 + 1] += (degree * -1); // 주어진 인덱스보다 열 인덱스가 1 크면 부호 반대
            sum[r2 + 1][c1] += (degree * -1); // 주어진 인덱스보다 행 인덱스가 1 크면 부호 반대
            sum[r2 + 1][c2 + 1] += degree; // 주어진 인덱스보다 행, 열 인덱스가 각 1씩 크면, 부호 그대로
        }

        for (int r = 1; r < n; r++) {
            for (int c = 0; c < m; c++) { // 상하로 계산 주석 #50 (Ry = Ry-1 + Ry)
                sum[r][c] += sum[r - 1][c];
            }
        }

        for (int c = 1; c < m; c++) {
            for (int r = 0; r < n; r++) { // 좌우로 계산 주석 #54 (Cx = Cx-1 + Cx)
                sum[r][c] += sum[r][c - 1];
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] + sum[i][j] > 0) answer++;
            }
        }
        return answer;
    }
}

// 누적합
// 행렬 방식으로 아래 방향으로 행 인덱스 증가, 오른쪽 방향으로 열 인덱스 증가

// 만약 (0, 0)을 sum하면 sum 배열은 아래와 같음
// 4 -4
// -4 4

// Ry = Ry-1 + Ry (단, y는 1 이상, R은 행, y = 0이라면 Ry = Ry) 으로 업데이트
// 4 -4
// 0  0

// Cx = Cx-1 + Cx (단, x는 1 이상, C는 컬럼, x = 0이라면 Cx = Cx) 으로 업데이트
// 4 0
// 0 0

 

 

2. 문제 접근 과정: 

 

해당 문제는 for문으로 범위 내 모든 탐색을 하게 된다면, skill의 행 길이 25만 개 중 모든 skill이 (0,0) ~ (1000, 1000) 범위를 업데이트를 하게 된다면 25만 * 1000 * 1000 = 250,000,000,000 번 계산을 하게 됩니다. 즉 최대 K * N * M 번을 계산해야 합니다.

 

이를 해결하기 위한 개념이 누적합 개념입니다. 처음에 이를 활용하지 못하여, 다른 분의 풀이를 보고 문제를 해결하였습니다.

해결과정은 다음과 같습니다.

 

skill의 하나의 행은 [type, r1, c1, r2, c2, degree]로 되어 있습니다. 

이때, r1 ~ r2, c1 ~ c2 범위로 바로 degree를 업데이트하지 않고 각 꼭짓점을 누적합을 위한 범위로 설정합니다.

 

주석과 마찬가지로 하나의 예를 들면 다음과 같습니다.

board : [[1, 1], [1, 1], [1, 1]]

skill : [[2, 0, 0, 0, 0, 4], [1, 0, 0, 1, 0, 2]]

 

board의 누적합을 위해 int [][] sum이라는 2차원 배열을 생성합니다.

누적합은 특정 x에 대한 범위 계산을 위해 하나의 열과 하나의 행이 더 필요합니다. 따라서 sum의 크기는

board.length + 1, board[0].length + 1입니다.

 

누적합에 입력은 x1, y1 이 시작점, x2, y2가 끝 점이라고 하면

 

(x1, y1) += n

(x1, y2 + 1) += -n  

(x2 + 1, y1) += -n

(x2 + 1, y2 + 1) += n입니다.  

 

먼저 skill의 0번째 인덱스에 대한 결과를 보면 (0, 0), (0, 0) 범위에 4를 더해야 합니다. 

 

 

이어서 skill의 1번째 인덱스에 대한 누적합을 합니다. 

 

(0, 0) , (1, 0)에 대한 -2의 누적합을 위해 아래처럼 계산을 합니다.

(0, 0) += -2

(0, 1) += -(-2)

(2, 0) += -(-2)

(2, 1) += -2

 

 

 

이제 누적합에 대한 상하, 좌우 공식으로 누적합에 대한 결과를 계산합니다.

Ry = Ry-1 + Ry(y는 1 이상, R은 행, y = 0 일 때, Ry = Ry)

Cx = Cx-1 + Cx(x는 1 이상, C는 열, x = 0 일 때, Cx = Cx)

 

 

상하 계산

 

 

 

좌우 계산

 

 

이 결과를 기존에 board 이차원 배열 각 원소에 대응하는 값을 더해주면 값을 얻을 수 있습니다.

 

 

누적 합에 대한 개념을 이해하는데 많이 헷갈렸습니다.

실제 로그를 찍어보고 그려보니 어떠한 방식으로 적용되는지 이해할 수 있었습니다.

이상으로 파괴되지 않은 건물 풀이를 마치도록 하겠습니다.

 

감사합니다.!