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

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=javascript

프로그래머스

 

ㅎㅎㅎㅎㅎㅎㅎ어려운 문제였다.

 

해당 문제는 "누적합"이라는 개념을 변형한 문제이다.

 

먼저 누적합은 아래와 같다.

 

1. 1차원

기존의 배열이 아래와 같다면

1

2

3

4

5

 

누적합은 아래와 같이 된다.

1

3

6

10

15

 

보기에도 알 수 있듯이 그저 앞의 값에 자기 자신을 더하면 된다.

따라서  arr 라는 배열의 길이가 n이라면

const n = arr.length;

// 누적합 배열 선언 후 0으로 초기화
const prefixArr = Array(n).fill(0);

// 첫번째 값은 누적할 필요가 없으므로 초기화
prefixArr[0] = arr[0];

for (let i = 1; i < n; i++) {
	// 이전 값 + 배열 값
	prefixArr[i] = prefixArr[i-1] + arr[i];
}

 

2. 2차원 누적합

기존의 배열이 아래와 같다면

1	2	3	4	5
6	7	8	9	10

 

누적합은 마찬가지로 아래와 같다

1	3	6	10	15
7	16	27	40	55

 

1차원 누적합보다 좀 더 어려워서 표를 하나 더 가져왔다.

기존의 배열이 아래라면

A	B
C	D

 

누적합은

A	A + B
A + C	A + B + C+ D

 

따라서 코드로 나타내기 위해

A + B + C + D = D + (A + B) + (A + C) - A

 

const n = arr.length;
const m = arr[0].length;

// 경계처리를 편하게 하기 위해 행과 열을 1 증가 (1-index)
const prefixArr = Array.from({length: n+1}, () => Array(m+1).fill(0));

// 첫 행 / 첫 열처리 따로하는 대신에 1-index로 활용
for (let r = 1; r <= n; r++) {
	for (let c = 1; c <= m; c++) {
    	prefixArr[r][c] = arr[r][c] + prefixArr[r-1][c] + prefixArr[r][c-1] - prefixArr[r-1][c-1];
    }
}

 

드디어 누적합 설명이 끝났다.

 

이제 문제에서 왜 누적합 개념이 필요한지 그리고 어떻게 사용해야 하는지 설명하려고 한다.

 

1. 누적합 개념이 필요한 이유

해당 문제는 r1, c1 ~ r2, c2까지 degree 만큼 내구성을 증가시키거나 감소시킨다.

따라서 매번 행과 열을 순회하며 내구성을 "직접" 증가시킨다면

최악의 경우 행의 길이 * 열의 길이 * skill의 길이 = 1000 * 1000 * 250000 이므로

시간복잡도가 터진다. 

(보통 1초당 100,000,000 1억 번이므로 터진다는 것을 알 수 있다.)

 

따라서 이를 누적합으로 해결한다.

행의 길이가 4, 열의 길이가 5일 때 (0-index)

(1, 1) ~ (2, 4)까지 2만큼 내구성을 증가시킨다고 가정하자.

그렇다면 먼저 (1, 1)에 2만큼 내구성을 저장한다.

누적합이기에 2는 이후의 행(1 이상)과 열(1 이상)에 모두 반영된다.

또한,  (2, 4)까지 반영되어야 하기 때문에 -2처리도 해야 한다.

1) 행의 경우 2행까지만 반영되어야 해서 3행에 -2 처리를 한다.

2) 열의 경우 4열까지만 반영되어야 해서 5열에 -2 처리를 한다.

(여기에서 알 수 있듯이 경계처리를 위해 행과 열의 길이를 각각 1씩 증가하였다.)

3) 그렇다면 누적합 배열의 (4, 5)에는 값이 -2가 되므로 또 다시 2를 더해준다

 

이 모든 것을 아래의 표에 연산해 두었다.

	0	1	2	3	4	5
0
1		2				-2
2
3
4		-2				2
5

 

어렵다. 보기 쉽게 해당 경우 누적합을 구해보면

	0	1	2	3	4	5
0
1		2	2	2	2	0
2		2	2	2	2	0
3		2	2	2	2	0
4		0	0	0	0	0
5

이렇게 나온다.

 

구하는 방법은 세 가지다.

1. 먼저 열을 반영하고 행을 구하는 경우

1) 누적합 열 반영

	0	1	2	3	4	5
0
1		2	2	2	2	0
2
3
4		-2	-2	-2	-2	0
5

2) 행 반영

	0	1	2	3	4	5
0
1		2	2	2	2	0
2		2	2	2	2	0
3		2	2	2	2	0
4		0	0	0	0	0
5

 

답이 잘나오게 된다.

 

2. 행 반영하고 열을 반영하는 경우

1) 행 반영

	0	1	2	3	4	5
0
1		2				-2
2		2				-2
3		2				-2
4		0				0
5

 

2) 열 반영

	0	1	2	3	4	5
0
1		2	2	2	2	0
2		2	2	2	2	0
3		2	2	2	2	0
4		0	0	0	0	0
5

답이 잘 나온다.

 

3. 기존의 2차원 누적합 연산

A + B + C + D = D + (A + B) + (A + C) - A

	0	1	2	3	4	5
0
1		2	2	2	2	0
2		2	2	2	2	0
3		2	2	2	2	0
4		0	0	0	0	0
5

 

 

정리하면

r1, c1 ~ r2, c2까지 degree만큼 내구성을 증가시키는 경우 코드는 아래와 같다.

prefixArr[r2+1][c2+1] += degree;
prefixArr[r1][c1] += degree;
prefixArr[r2+1][c1] -= degree;
prefixArr[r1][c2+1] -= degree;

 

그리고 누적합 연산 (세 가지 중 하나를 활용하면 된다.)

 

휴 드디어 끝이 났다. 아래는 코드이다. 나는 열 -> 행으로 누적합을 구했다.

 

/*
2차원 누적합

경계처리 할 것

길이 가로 세로 하나씩 늘려서 경계처리
*/

function solution(board, skill) {
    const n = board.length;
    const m = board[0].length;
    
    // 경계처리 편하게 하기 위해 +1
    const prefixSum = Array.from({length: n+1}, () => Array(m+1).fill(0));
    
    for (const [type, r1, c1, r2, c2, degree] of skill) {
        const attack = type === 1 ? -degree : degree;
        
        prefixSum[r2+1][c2+1] += attack;
        prefixSum[r1][c2+1] -= attack;
        prefixSum[r2+1][c1] -= attack;
        prefixSum[r1][c1] += attack;
    }
    
    // 누적합 - 열 
    for (let r = 0; r <= n; r++) {
        for (let c = 1; c <= m; c++) {
            prefixSum[r][c] += prefixSum[r][c-1];
        }
    }
    
    // 누적합 - 행
    for (let r = 1; r <= n; r++) {
        for (let c = 0; c <= m; c++) {
            prefixSum[r][c] += prefixSum[r-1][c];
        }
    }
    
    let answer = 0;
    
    // 결과
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < m; c++) {
            if (prefixSum[r][c] + board[r][c] > 0) answer++;
        }
    }
    
    return answer;
}