[프로그래머스] 파괴되지 않은 건물(JAVA), 2차원 배열 누적합, 2022 KAKAO BLIND RECRUITMENT

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

프로그래머스

누적합을 이용해서 시간복잡도를 줄이는 문제는 처음봤다...
정확도 테스트케이스는 간단히 브루트포스로 풀면 맞출 수 있으나 그 경우 O(N*M*K) 가 되어 효율성 테스트케이스가 모두 시간초과가 난다.

효율성 테스트를 통과시키기 위해선 누적합 개념을 알고 있어야 한다.
(효율성 정답률이 2%도 안되는 걸 보아 개념을 알았어도 이용할 생각을 하기는 쉽지 않아 보인다..^^)

누적합

arr = [3, 5, 7, 1, 4]
sum_list = [3, 8, 15, 16, 20]

누적합이란 위와 같이 i 번째 까지의 원소의 값을 누적한 값을 말한다.
누적합을 이용해 연속된 구간의 합을 구하는 시간을 줄일 수 있다.

sum_list[i]는 arr[0]부터 arr[i]까지의 모든 원소의 합을 값으로 갖는다. 또한 arr[i]부터 arr[j]까지의 부분합은 sum_list[j] - sum_list[i-1]로 정의할 수 있다.

1차원 배열일 경우 반복문을 통한 구간합이 O(n)이고, 2차원 배열은 O(n^2)이다. 하지만 위 특징을 사용해서 연속된 임의의 구간의 합을 O(1)의 시간복잡도로 구할 수 있다.

2차원 누적합

이차원 배열 a(i, j)와 누적합 배열 S(i, j)가 있다고 가정하자.

좌측 상단을 a(1, 1)이라 할 때, S(i, j)는 a(1, 1)과 a(i, j)를 양 대각 끝 꼭짓점으로 하는 직사각형 범위 면적 안의 모든 a원소의 합으로 정의된다.

따라서 a(2, 2) ~ a(3, 3)의 부분합을 구해보자.

S(3, 3) 값에서 S(1, 3) 값을 빼고, S(3, 1)값을 뺀다. 이때 S(1, 1)은 S(1, 3)과 S(3, 1)에 의해서 2번 빼진 셈이니 S(1, 1)을 더해주면 초록색 부분의 구간합이 된다.

이차원 누적합 배열 구하기

2차원 배열의 누적합 배열을 구하는 방법은 위와 같다.

1. a(i, j)에서 행방향으로 누적합을 구한다.
2. 행 누적합에 대해서 열방향으로 누적합을 구한다.

---

누적합을 이용한 문제 풀이

다시 문제로 돌아와서, 누적합의 성질을 이용하면 "a번째 원소부터 b번째 원소까지 c만큼의 변화를 주는 것" 을 매번 탐색하지 않고도 한꺼번에 처리할 수 있다.

[1,2,4,8,9] 의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황

위의 예시를 들어보자. 배열을 [-1,0,2,6,9]로 만들고 싶은 상황이다.
0번째부터 3번째 원소까지 반복문을 사용해 2만큼 빼주는 방법이 있지만, 이 방법은 O(M)의 시간 복잡도가 걸린다.

누적합을 이용

1. [-2,0,0,0,2]를 저장한 새로운 배열을 만든다.
2. 이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 된다. (*0번째부터 3번째 원소까지 2만큼 빼는 상황)
3. 초기 배열인 [1,2,4,8,9]과 더해주면 [-1,0,2,6,9]를 얻는다.

즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 뺀 배열을 이용한다.

이를 활용하면 여러 변화를 한꺼번에 적용시킬 수 있다.
예컨데 위의 상황에서 1번째부터 2번째 원소까지 4를 더하는 조건이 추가된다면 새로운 배열은 [-2,4,0,-4,2] 가 될 것이다.
이 배열의 누적합 배열을 구하면 [-2,2,2,-2,0] 이 된다. 이를 초기 배열에 더하면 [-1,4,6,6,9] 이 된다.

2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우

배열의 행만 따로 봐서 위에서 설명한 아이디어를 하나의 행씩 적용시키면, 1차원 배열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 3개의 행에 적용시키는 것이 된다.

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

위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화와 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -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을 한 것과 같다.

위 배열을 위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있다.

n n n 0
n n n 0
n n n 0
0 0 0 0

이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있다.
따라서 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸린다.
해당 배열을 누적합 배열로 바꾸는 과정이 행과 열을 각각 누적합 해줘야 하기 때문에 O(N * M)이 걸린다.

따라서 O(K + N * M)으로 문제를 해결할 수 있다.

---

2번 테스트 케이스 예시

(1,1)부터 (2,2)까지 -4만큼 변화를 줘야 한다.
(배열의 (1,1)과 (3,3)에 -4, 배열의 (1,3)과 (3,1)에 4만큼 변화를 준다.)

     0    0    0    0
     0   -4    0    4
     0    0    0    0
     0    4    0   -4

 

(0,0)부터 (1,1)까지 -2만큼 변화를 줘야 한다.
(배열의 (0,0)과 (2,2)에 -2, 배열의 (0,2)과 (2,0)에 2만큼 변화를 준다.)

    -2    0    2    0
     0   -4    0    4
     2    0   -2    0
     0    4    0   -4

 

(2,0)부터 (2,0)까지 +100의 변화를 줘야 한다.
(배열의 (2,0)과 (3,1)에 100, 배열의 (2,1)과 (3,0)에 -100만큼 변화를 준다.)

    -2    0    2    0
     0   -4    0    4
    102  -100 -2    0
   -100   104  0   -4

 

이 배열을 이제 위에서 아래로 누적합

-2    0    2    0
-2   -4    2    4
100  -104  0    4
 0    0    0    0

 

왼쪽에서 오른쪽으로 누적합

-2   -2    0    0
-2   -6   -4    0
100  -4   -4    0
 0    0    0    0

 

누적합 배열을 board와 합친다

1 2 3         -2  -2   0        -1  0  3
4 5 6    +    -2  -6  -4    =    2 -1  2
7 8 9         100 -4  -4        107 4  5

 

코드

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int colSize = board[0].length;
        int rowSize = board.length;

        int[][] save = new int[rowSize + 1][colSize + 1];
        for (int[] o : skill) {
            int x1 = o[1];
            int y1 = o[2];
            int x2 = o[3];
            int y2 = o[4];
            int c;
            if (o[0] == 1) {
                c = -o[5];
            } else {
                c = o[5];
            }
            save[x1][y1] +=c;
            save[x1][y2 + 1] -=c;
            save[x2 + 1][y1] -=c;
            save[x2 + 1][y2 + 1] +=c;
        }
        for (int j = 0; j < colSize; j++) {
            for (int i = 1; i < rowSize; i++) {
                save[i][j] += save[i - 1][j];
            }
        }

        for (int i = 0; i < rowSize; i++) {
            for (int j = 1; j < colSize; j++) {
                save[i][j] += save[i][j - 1];
            }
        }

        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                board[i][j] += save[i][j];
                if (board[i][j] > 0) answer++;
            }
        }

        return answer;
    }
}

 

---

Reference.

• https://velog.io/@ohdowon064/Algorithm-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EB%B6%80%EB%B6%84%ED%95%A9-%EB%88%84%EC%A0%81%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0
• https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC