[JS] 파괴되지 않은 건물

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

프로그래머스

 

 

문제 자체는 매우 심플하지만 시간초과를 해결하기 위해서 독특한 방법이 필요한 문제였다.

 

스스로 고민을 좀 해보았지만 방법이 떠오르지 않아서 카카오에서 제공하는 공식 해설을 보고 방법을 이해한 후 구현만 직접 해보며 해결하였다.

 

문제의 핵심은 누적합을 이용하는 것이다!

 

예를 들어서 [ 1 , 3, 5, 2, 5 ] 이렇게 5개의 수가 있는 1차원 배열을 생각해보자.

 

해당 수에서 index가 1~3 까지에 2라는 수를 더하려면 보통은 반복문을 활용해서 일일히 더해줄 것이다. 이번엔 아래 방법을 생각해보자.

 

[ 0, 0, 0, 0 ,0 ] 와 같이 새로운 배열을 하나 만들고 index가 1번째와 3+1번째에 2와 -2를 넣는다.

[ 0 ,2 ,0, 0, -2] <-- 이렇게 나올 것이다.

 

이후 해당 배열을 좌측부터 누적합을 진행하여 배열을 만들어 준다.

 

[ 0, 2, 2 ,2 ,0 ] 

위 배열을 원본배열과 합치면 1~3까지 2를 더한 배열이 나오게 된다.

 

 

A~B까지 C라는 값을 더하기 위해서는 누적합의 배열에 A엔 C , B+1엔 -C 를 넣어준다 (B+1이 인덱스를 넘어간다면 넣지 않는다.)

 

 

언뜻 보면 결국 누적합이란 개념덕에 배열을 한바퀴 돌아야 하는것 똑같지 않나? 라고 생각할 수 있다.

하지만 이렇게 A~B사이의 값을 구하는 로직을 1000번 해야한다고 생각해 보자.

 

 

 

1. 일반적인 반복문을 활용하는 경우 (배열의 크기를 V라고 두자)

 

A~B 까지 순회하면서 값을 반복하는걸 1000번 해야한다.

=> 시간복잡도가 V * 1000이 된다.

 

2. 누적합 배열을 활용하는 경우

누적합 배열에 A,B+1에 값만 넣고 마지막에 한번만 누적합을 구해주면 된다.

=> 시간복잡도가 V + 1000 가 된다.

 

 

 

이 개념을 그대로 2차원 배열에 넣는다면,

 

(A,B) ~ (C,D) 로이루어지는 사각형에 E라는 값을 더해준다면

 

2차원 누적합 배열을 만들고

 

(A,B) -> E

(A,D) -> -E

(C,B) -> -E

(C,D) -> E

 

라는 값을 넣어 준 후, 좌->우 상->하 혹은 상->하 좌->우 순서로 누적합을 순서대로 결정하면 된다. (상-하 , 좌-우 순서는 상관없음)

 

 

누적합을 활용해서 이런것도 할수있는지는  첨 알았다.

 

function solution(board, skill) {
    const rLen = board.length
    const cLen = board[0].length
    
    const cumSumAry = [...Array(rLen)].map(_ => Array(cLen).fill(0))
    
    
    for (const [type,r1,c1,r2,c2,degree] of skill){
        const attack = type===1 ? -1 : 1
        cumSumAry[r1][c1] += attack * degree
        if (c2+1<cLen) cumSumAry[r1][c2+1] += -1 * attack * degree 
        if (r2+1<rLen) cumSumAry[r2+1][c1] += -1 * attack * degree
        if (c2+1<cLen && r2+1<rLen) cumSumAry[r2+1][c2+1] += attack * degree
    }
    
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 1 ; j < cLen ; j++){
            cumSumAry[i][j] += cumSumAry[i][j-1]
        }
    }
    for (let i = 1 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            cumSumAry[i][j] += cumSumAry[i-1][j]
        }
    }
    
    
    let ret = 0
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j< cLen ; j++){
            if (board[i][j] + cumSumAry[i][j] >0) ret ++
        }
    }
    return ret
}