(프로그래머스 KAKAO JS)파괴되지 않은 건물

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

코딩테스트 연습 - 파괴되지 않은 건물

 

새로운 알고리즘을 배웠다.

누적합을 효율적으로 처리할 수 있는 알고리즘이다.

 

IMOS 알고리즘이라고,

아래 블로그에서 설명이 자세하게 잘 나와있어서 참고해서 풀 수 있었다.

https://nicotina04.tistory.com/163

imos법 imos method いもす法

 

우선 imos를 처리하기 위한 배열을 선언해야 한다.

imos 배열의 크기는 주어진 board의 행과 열의 +1 크기만큼 선언한다.

 

skill을 순회하면서 각 좌표에 degree를 처리한다.

type = 1이면 공격이기 때문에 -degree, 2면 회복이기 때문에 degree를 imos에 적용하면 된다.

단, imos 규칙에 따라 4개의 좌표에 알맞게 적용해야 한다.

 

imos[r1][c1] += type === 1 ? -degree : degree

imos[r1][c2 + 1] += type === 1 ? degree : -degree

imos[r2 + 1][c1] += type === 1 ? degree : -degree

imos[r2 + 1][c2 + 1] += type === 1 ? -degree : degree

 

지그재그로 잘 나와있어서 외우기 쉬울 것 같다.

 

imos 적용이 끝났으면 누적합을 행과 열에 대해 진행해주면 된다.

이후 board를 순회하면서 imos에 저장된 누적합을 더해 1 이상인 경우 answer++을 해주면 된다.

 

const solution = (board, skill) => {
    let answer = 0;
    const row = board.length;
    const col = board[0].length;
    const imos = Array.from({length: row + 1}, () => Array(col + 1).fill(0));
    
    for(let i = 0; i < skill.length; i++){
        const [type, r1, c1, r2, c2, degree] = skill[i];
        
        imos[r1][c1] += type === 1 ? -degree : degree;
        imos[r1][c2 + 1] += type === 1 ? degree : -degree;
        imos[r2 + 1][c1] += type === 1 ? degree : -degree;
        imos[r2 + 1][c2 + 1] += type === 1 ? -degree : degree;
    }
    
    for(let i = 0; i < row; i++){
        let sum = 0;
        
        for(let j = 0; j < col; j++){
            sum += imos[i][j];
            imos[i][j] = sum;
        }
    }
    
    for(let i = 0; i < col; i++){
        let sum = 0;
        
        for(let j = 0; j < row; j++){
            sum += imos[j][i];
            imos[j][i] = sum;
        }
    }
    
    for(let i = 0; i < row; i++){
        for(let j = 0; j < col; j++){
            board[i][j] += imos[i][j];
            
            if(board[i][j] > 0){
                answer++;
            }
        }
    }
    
    return answer;
}