[프로그래머스] 파괴되지 않은 건물

 

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

프로그래머스

 

프로그래머스에서 제공되는 레벨3 문제이며, 2022 카카오 블라인드 테스트에서도 출제된 문제다.

해당 문제는 누적합을 기본적으로 알아야 해결 가능하며, 2차원 배열에서의 누적합을 알아야 효율성 테스트에서 통과 가능하다.

 

먼저, 누적합이라는 개념을 먼저 알아보자.

 

예를 들어, 아래와 같은 배열이 존재한다고 가정한다.

1

2

3

4

5

6

 

여기서 1번째 인덱스부터 3번째 인덱스까지 모두 2만큼 뺀다고 가정해보자.

 

1

0

1

2

5

6

 

if. 배열 원소개수가 100만 이상, 1000만 이상이라고 하면 순차적으로 모두 더해주는 것은 매우 어려운 작업이다.

(특히 연산을 수행하면서 이중 루프를 돈다면 더더욱 효율성 테스트를 통과하기 어려울 것이다.)

 

효율성 테스트를 통과하기 위해서 대체로 사용하는 방법은 바로 dynamic programming 이다.

 

dynamic programming 은 이전 과정의 결과값을 현재 결과에 반영하는 것에 중점을 둔다.

 

위 과정에선 어떻게 dynamic programming 을 활용할 것인지 고민해보자.

 

우선, 1번째 인덱스에서 3번째 인덱스까지 모두 2를 더한다고 하면, 1번째 인덱스에 2를 넣고, 3번째 다음 인덱스에 -2 를 넣는 방식이다.

(배열 원소 개수가 n개라고 할때, 누적합 배열은 n+1개의 원소를 가지고 있어야 한다)

 

0

2

0

0

-2

0

0

 

저도 처음엔 누적합 원리에 대해서 한참 생각해보다가 아래와 같은 공식을 보니 이해가 되었다.

• dp[i] += dp[i-1]

 

위 공식에 의해서 배열값은 아래와 같이 처리된다.

0

2

2

2

0

0

0

 

정확하게 누적되는 값들이 반영되는 배열이 만들어진다!

 

이를 2차원 배열로 응용해보자.

 

(1,1) 부터 (2,2) 에 해당되는 누적합을 구해보자. 구간 내에 모두 2를 더한다.

원리는 위에서 설명한 것과 유사하다.

0	0	0	0
0	2	0	-2
0	0	0	0
0	-2	0	2

 

이 경우에는 좌->우, 상 -> 하 모두 누적합 계산을 해주어야 한다.

 

좌 -> 우

0	0	0	0
0	2	2	0
0	0	0	0
0	-2	-2	0

 

상 -> 하

0	0	0	0
0	2	2	0
0	2	2	0
0	0	0	0

 

문제 유의사항으로 skill 최대 개수가 25만개이고, 행 최대개수가 1000, 열 최대개수가 1000 이라는 점이다.

즉 skill 최대 개수 * 행 혹은 열 최대개수 연산을 수행할 경우 효율성 테스트에서는 당연히 통과 못한다.

 

효율성 테스트를 통과하기 위해서는 2차원 배열의 누적합을 활용해야 하고,  좌->우, 상->하 누적합 처리를 해야 통과 가능합니다.

 

(Example Code)

    public static int solution(int[][] board, int[][] skill) {
        int answer = 0;

        int rows = board.length;
        int cols = board[0].length;

        int[][] dp = new int[rows+1][cols+1];

        for (int i = 0; i < skill.length; i++) {
            int degree = skill[i][0] == 1 ? -skill[i][5] : skill[i][5];
            int r1 = skill[i][1];
            int r2 = skill[i][3];
            int c1 = skill[i][2];
            int c2 = skill[i][4];
            dp[r1][c1] += degree;
            dp[r2+1][c1] -= degree;
            dp[r1][c2+1] -= degree;
            dp[r2+1][c2+1] += degree;
        }

        // left -> right
        for (int i = 0; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] += dp[i][j-1];
            }
        }

        // up -> down
        for (int j = 0; j < cols; j++) {
            for (int i = 1; i < rows; i++) {
                dp[i][j] += dp[i-1][j];
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] + dp[i][j] > 0) answer++;
            }
        }

        return answer;
    }