[CodeKata] 프로그래머스(Lv3) : 파괴되지 않은 건물

 

🥋 Oooth More!! (Level 3) 

입출력 예 #2 케이스는 문제 링크를 참고해주세요!

 

 

 

🧮 풀이

매 skill 마다 해당하는 영역을 이중순회 하는 것은 비효율적일 것이라고 예상했다.

그래서 반대로, 매 칸을 순회하면서 각 칸마다 skill들의 적용여부에 따른 남은 내구도를 판단하는 방법을 구현했다.

정확성 테스트는 통과했으나, 효율성 테스트를 역시 통과하지 못하며 더 나은 방법을 공부해야했었다.

function solution(board, skill) {
  let answer = 0
    
  for (let i = 0 ; i < board.length ; i++) {
    for (let j = 0 ; j < board[0].length ; j++) {
					
      let life = skill.reduce((acc,cur) => {
        const [type, r1, c1, r2, c2, degree] = cur;
        return !(i >= r1 && i <= r2 && j >= c1 && j <= c2) ? acc : type === 1 ? acc-degree : acc+degree
      }, board[i][j])
      if (life > 0) answer++
    }
  }
    
  return answer;
}

• answer는 내구도가 살아있는 건물들의 개수를 누적할 변수이다.
• board를 이중 for문으로 순회한다. life는 해당 칸의 내구도로 reduce()로 계산하며, 초기값은 현재 내구도인 board[i][j] 다.
• 현재값 cur의 각 값을 구조 분해 할당한다. i, j 가 각각 r1~r2, c1~c2 범위에 포함되지 않았다면 기존 acc, 포함된다면 type에 따라 acc에 degree를 더하거나 뺀 값을 반환한다.
• 위를 통해 누적된 life가 해당 칸의 내구도인 것이다. 이 값이 0보다 큰 경우 answer에 1을 더한다.

 

 

 

🖇 리뷰

누적합을 효율적으로 구하는 IMOS 알고리즘을 적용한 풀이라고 한다. 모범답안을 해석한 뒤, 알고리즘도 공부해보았다.

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;
}

* 출처 : https://eunchanee.tistory.com/628  

 

1. 풀이 준비

• answer는 마지막에 내구도가 남은 건물들의 개수를 누적할 정답 변수이다. row, col은 각각 board의 행, 열 길이다.
• imos는 누적합을 계산하는 이중배열로, 0으로 초기화하며 board보다 행과 열 길이가 각각 1씩 많다. (누적값을 세팅할때 끝점+1까지 보기에)
• skill을 순회하며 imos를 세팅한다. r1, c1, (r2+1), (c2+1) 로 만들어지는 4개 좌표에 누적값과 이를 원복하는 -(누적값)을 아래와 같이 세팅한다.
  • imos[r1][c1]은 시작점으로, 여기서부턴 값이 누적되어야한다. type이 1일 경우 음수, 아니면 양수의 degree를 넣어준다.
  • imos[r1][c2+1], imos[r2+1][c1]은 각각 가로합과 세로합이 끝나는 다음지점으로, 여기서부턴 이전 누적값의 영향을 받지 않기 위해 반대양/음 의 degree를 넣어준 것이다.
  • imos[r2+1][c2+1]는 위 설정이 2번 겹치는 지점이다. 반대양/음 값을 하나 지우기 위해 본래 degree를 세팅한다.

 

2. IMOS 누적값 계산

• 먼저, 각 행(i)의 누적합을 계산한다. 시작값(sum) 0에서, 각 열(j)을 순회하며 현재 imos[i][j]를 더하고, 현재좌표의 누적합에 sum을 반영한다.
• 다음, 각 열(j)을 다시 누적합한다. 마찬가지로 sum 0부터, 각 행(i)를 순회하며 현재 imos[j][i]를 더하고, 현재좌표의 누적합을 sum으로 다시 갱신한다.

 

3. 파괴되지 않은 건물 확인

• 이제, board 행과 열을 이중순회하며, 현재 내구도(board[i][j])에 imos[i][j] 스킬 누적합을 더한다. 이 값이 0보다 크면 answer에 1을 더한다.
• 이렇게 누적된 answer 값을 최종 반환한다.

 

 

* IMOS 알고리즘

 

IMOS 명칭의 유래는 명확하지 않으나 일본에서 온 것으로 추정된다. 

보통 2차원 이상의 반복적인 누적합 계산에서, 시간복잡도가 누적합 길이(T) x 누적합 개수(N)가 되는 것을 효율화하기 위한 알고리즘이다.

 

아래는 가게의 피크타임을 계산하는 예시이다. 각 손님들이 방문하는 시간대를 제시하고, 가장 몰리는 시간대가 언제인지 확인하는 것이다.

 

 

기존의 누적합의 경우, 각 손님의 방문시간을 확인하여 전체 시간대에 손님수 1을 더해줘야 한다.

이렇게 되면, 시간복잡도 Q는 시간대의 길이(T) x 손님의 수(N) 로 상당한 편이다.

또한, 손님의 수나 해당 손님의 방문시간이 길어질수록 연산량이 복잡해진다는 단점이 존재한다.

 

IMOS는 방문시간 전체가 아닌, 입장시간(+)과 퇴장시간(-) 만을 설정하여 이를 통해 누적합을 계산하는 방법이다.

누적값(최초 0)에, 현재 시간대에 입장한 손님이 있다면 1을 더해놓는다. 이 값으로 현재 IMOS 좌표에 넣어준다.

다음 칸부터는, 이전칸까지의 누적값에 현재 시간대의 입장/퇴장 여부를 더하거나 빼면서 해당 IMOS 좌표를 누적값으로 넣어주면 된다.

 

 

[출처]

- nicotina04 님의 블로그 : https://nicotina04.tistory.com/163  

- black-hair 님의 블로그 : https://black-hair.tistory.com/147

 

---

 

이번 문제처럼, board(2차원 배열)에서 복수의 영역에 해당하는 값들을 각각 board에 누적하다보면,

이중순회가 영역의 크기 x 영역의 수 만큼 순회한다는 비효율성이 발생한다.

이를, 영역의 시작점과 끝점(+1)을 각각 값의 추가와 제거로 설정한 뒤, 행과 열을 누적해나가며 각 칸의 누적값을 계산할 수 있다!

 

IMOS 알고리즘은, 피크타임 계산, board 영역 누적합 계산 등에 유용하게 쓰일 수 있기에 기억해놓아야겠다!