[Refresh ! 코딩 테스트 / js] -파괴되지 않은 건물

• 이문제는 딱봐도 완.탐으로 풀면 시간 초과 될꺼 같아서 30분 동안 고민하다가 답지를 봤다.
• 누적합이라는 것을 새로 알게 되었다..

문제풀이

• (0,0) 부터 (3,4) 까지 공격을 하면 이부분의 숫자들이 작아짐
• 완탐으로 하면n^3 이 되서 시간초과
• 누적합을 사용하면 0(k+ N^2) 이됨

WHAT IS 누적합?

• 누적합은 방어벽 +DP 문제

• 이전의 값이 현재의 값을 채워주는데 . 방어벽은 여기까지만 채워주겠습니다. 하는 의미이다.

• 왼 -> 오

• 위 -> 아래

• 식으로 직접 해보니 . 무슨 말인지 알겠다.

나의 풀이

function solution(board, skill) {
// 누적합으로 푸는 문제. 
    let b_g= board[0].length+1;
    let b_s= board.length+1;
    
    let arr_board= Array.from({length:b_s},()=>Array(b_g).fill(0));
    // 배열 생성
    skill.forEach((el)=>{
        let [type,s1,s2,e1,e2,degree]=el;
        degree=type==1?degree*-1:degree;
        //degree 공격 점수 or 회복점수
        arr_board[s1][s2]+=degree;
        arr_board[s1][e2+1]+=degree*-1;
         arr_board[e1+1][s2]+=degree*-1;
        arr_board[e1+1][e2+1]+=degree;
        
    })
    //누적합 세팅완료
    
    //왼쪽에서 오른쪽으로 가는 코드
    for(var i=0; i<b_s; i++){
        for(var g=1; g<b_g; g++ ){
            arr_board[i][g]+=arr_board[i][g-1]
        }
    }
    
    //위에서 아래로 가는 코드 
    for (let ii = 1; ii < b_s; ii++) {
        for (let gg = 0; gg < b_g; gg++) {
            arr_board[ii][gg] += arr_board[ii - 1][gg];
        }
    }
   // 누적합 적용
    let answer=0;
    
    for(var iii=0; iii<b_s-1; iii++){
        for(var ggg=0; ggg<b_g-1; ggg++){
            board[iii][ggg]+=arr_board[iii][ggg]
            if(board[iii][ggg]>0){
                answer+=1;
            }
        }
    }
    return answer;
    
}

ㅇ ㅕ담

• 요즘 클린 코드에 대해서 공부를 해야되겠다 생각이 들었다..
  프로그래머 한테 중요한건 나만이 알수 있는 코드가 아니고 딱 봤을때 뭘 의미하는지를 알수 있는 협업성이라는것을 ㅠㅠ 깨닭음..
• 나.. 취업하루 잇을까..ㅠㅠㅋㅋㅋ