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

🚩문제 주소

📄풀이

누적합

처음 문제를 보고 해석했을 때, 떠올린 풀이인데 정확성은 맞출 것 같았지만 효율성은 통과하지 못할 것 같았습니다. 그래도 일단 정확성이라도 맞추자라는 생각으로 푼 풀이입니다.

const calculate = (board, r1, c1, r2, c2, degree) => {
    for (let i=r1; i<=r2; i++) {
        for (let j=c1; j<=c2; j++) {
            board[i][j] += degree;
        }
    }
}

const solution = (board, skill) => {
    skill.forEach(v=>{
        const [type, r1, c1, r2, c2, degree] = v;
        calculate(board, r1, c1, r2, c2, type===1 ? -degree : degree);
    });
    
    return board.map(v=>v.filter(v2=>v2>0).length).reduce((acc,cur)=>acc+cur);
}

정확성은 전부 맞췄지만 효율성은 전부 나가리였습니다.
해결 방법이 너무 떠오르지 않아서 카카오 기술 블로그에서 해설을 봐버렸습니다. 카카오 해설

누적합의 개념은 알고 있었지만 2차원 배열을 활용해 누적합하는 것은 정말 신기했습니다.
그리고 더욱 더 공부를 해야된다는 것을 느꼈습니다...

(0,0)부터 (2,2)까지 n만큼의 변화를 줘야한다면

											  아래, 오른쪽으로 누적합한 결과
[0, 0 ,0, 0]	=> 	 	[n, 0, 0, -n]	   => 		[n, n, n, 0]
[0, 0 ,0, 0]		 	[0, 0, 0, 0]	 	    	[n, n, n, 0]
[0, 0 ,0, 0]		 	[0, 0, 0, 0]				[n, n, n, 0]
[0, 0 ,0, 0]		 	[-n, 0, 0, n]				[0, 0, 0, 0]
 

이런 식으로 (r1, c1) += n, (r2+1, c1) += -n, (r1, c2+1) += -n, (r2+1, c2+1) += n 을 하고 아래와 오른쪽 방향으로 각각 누적합을 해주면 됩니다.

누적합한 결과를 기존의 board와 합쳐주게 되면 최종적으로 공격과 회복이 완료된 board가 나오게 되고 0 이하로 내려간 칸의 갯수를 세주어서 반환한다면 정답이 나오게 됩니다.

👨‍💻코드

const prefixSum = (pSum, skill) => {
    skill.forEach(v=>{
        const [type, r1, c1, r2, c2, degree] = v;
        const d = type === 1 ? -degree : degree;
        pSum[r1][c1] += d;
        pSum[r2+1][c1] += -d;
        pSum[r1][c2+1] += -d;
        pSum[r2+1][c2+1] += d; 
    });
    for (let r = 0; r < pSum.length; r++) { // 아래로 누적합
        for (let c = 1; c < pSum[0].length; c++) {
            pSum[r][c] += pSum[r][c - 1];
        }
    }
    for (let r = 1; r < pSum.length; r++) { // 오른쪽으로 누적합
        for (let c = 0; c < pSum[0].length; c++) {
            pSum[r][c] += pSum[r - 1][c];
        }
    }
}

const solution = (board, skill) => {
    const pSum = Array.from({length: board.length+1}, ()=>Array(board[0].length+1).fill(0));
    prefixSum(pSum, skill);
    
    for (let r = 0; r < board.length; r++) {
        for (let c = 0; c < board[0].length; c++) {
            board[r][c] += pSum[r][c];
        }
    }
    
    return board.map(v=>v.filter(v2=>v2>0).length).reduce((acc,cur)=>acc+cur);
}