문제 링크

프로그래머스 문제

풀이

당연하지만 문제를 포자마자 보이는 단순한 풀이로는 시간초과가 발생하게 된다.

function solution(board, skill) {
    var answer = 0;
    
    for(let i=0; i< skill.length; i++){
        const [type, r1, c1, r2, c2, degree] = skill[i]
        
        for(let x = c1; x <=c2; x++){
            for(let y = r1; y<=r2; y++){
                if(type === 1){
                    board[y][x]-= degree;
                }else if(type === 2){
                    board[y][x]+= degree;
                }
            }
        }
    }
    for(let i=0; i < board[0].length; i++){
        for(let j=0; j< board.length; j++){
            if(board[j][i] > 0){
                answer+=1;
            }
        }
    }
    
    return answer;
}

역시나 맞이하게된 시간초과...

그다음 사용하게 된 방법은 누적합 입니다.
적절한 좌표값들을 기준으로, 계산이 될 degree들을 배열에 만들어 둔 뒤 행과 열을 반복하며 최종적으로 계산이 가능한 값을 남기는 방법이었습니다.

코드

function solution(board, skill) {
    var answer = 0;
    
    const YLen = board.length;
    const XLen = board[0].length;
    
    const map = new Array(YLen+1).fill(0).map(()=> new Array(XLen+1).fill(0))
  
    for(let i=0; i<skill.length; i++){
        const [type , r1, c1, r2, c2, degree] = skill[i].map(v => +v);
        
        
        if(type === 1){ // 공격 내구도를 낮춘다
            // 왼쪽 위
            map[r1][c1] -= degree
            // 오른쪽 위
            map[r2+1][c1] += degree
            // 왼쪽 아래
            map[r1][c2+1] += degree
            // 왼쪽 아래
            map[r2+1][c2+1] -= degree
        }else if(type === 2){ // 회복시킨다.
            // 왼쪽 위
            map[r1][c1] += degree
            // 오른쪽 위
            map[r2+1][c1] -= degree
            // 왼쪽 아래
            map[r1][c2+1] -= degree
            // 왼쪽 아래
            map[r2+1][c2+1] += degree
        }
    }
    
    for(let y =0; y< map.length; y++){
        for(let x =1; x < map[0].length; x++){
            map[y][x] += Number(map[y][x-1]) 
        }
    }
    
    
    for(let y =1; y< map.length; y++){
        for(let x =0; x < map[0].length; x++){
            map[y][x] += Number(map[y-1][x] )
        }
    }
    
    for(let y =0; y< board.length; y++){
        for(let x =0; x < board[0].length; x++){
            if(board[y][x] + map[y][x] >0){
                answer++
            }
        }
    }
    
    return answer;
}