[Javascript/PGS] Lv.3 : 파괴되지 않은 건물 (2022 KAKAO)

 

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

프로그래머스

---

프로그래머스 레벨 3. 카카오 기출

쉬워보이는 문제인데, 효율성 테스트 때문에 애먹었다.

 

정석적인 풀이는 누적합 사용이었다!

다른 맵 문제에서도 쓰일 수 있을 것 같아서, 잘 알아둬야겠다.

 

 

 

출처 카카오테크 문제 풀이 : https://tech.kakao.com/posts/488

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설 - tech.kakao.com

 

 

 

1. 브루트 포스 : 효율성 0%🫠

let gameMap;

const updateMap=(type,r1,c1,r2,c2,degree)=>{
    for(let i=r1; i<=r2; ++i){
        for(let j=c1; j<=c2; ++j){
            if(type==1) gameMap[i][j] -= degree;
            if(type==2) gameMap[i][j] += degree;
        }
    }
}

const countSaveBuilding=()=>{
    let x = gameMap.length;
    let y = gameMap[0].length;
    let ans = 0;
    for(let i=0; i<x; ++i){
        for(let j=0; j<y; ++j){
            if(gameMap[i][j]>0) ans++;
        }
    }
    return ans;
}

function solution(board, skill) {
    var answer = 0;
    gameMap = board;
    for(let i=0; i<skill.length; ++i){
        let [type, r1, c1, r2, c2, degree] = skill[i];
        updateMap(type,r1,c1,r2,c2,degree);
    }
    answer = countSaveBuilding();
    return answer;
}

 

 

2. 누적합 사용 정답 풀이‼️

function solution(board, skill) {
    var answer = 0;
    let x = board.length;
    let y = board[0].length;
    let gameMap = Array.from({length:x+1},()=>new Array(y+1).fill(0));
    
    for(let [type, r1, c1, r2, c2, degree] of skill){
        const d = (type == 1 ? -1*degree : degree);
        gameMap[r1][c1] += d;
        gameMap[r1][c2+1] -= d;
        gameMap[r2+1][c1] -= d;
        gameMap[r2+1][c2+1] += d;
    }
    
    for(let i=0; i<=x; ++i){
        for(let j=1; j<=y; ++j){
            gameMap[i][j] += gameMap[i][j-1];
        }
    }
    for(let j=0; j<=y; ++j){
        for(let i=1; i<=x; ++i){
            gameMap[i][j] += gameMap[i-1][j];
        }
    }
    
    for(let i=0; i<x; ++i){
        for(let j=0; j<y; ++j){
            board[i][j] += gameMap[i][j];
            if(board[i][j]>0) answer++;
        }
    }
    
    return answer;
}