[JS] 파괴되지 않은 건물

문제

프로그래머스

 

풀이

우선 이 문제를 만든 카카오에 대해 크나 큰 존경이 들었다. 이게 참... 확실히 굉장한 사람들이 모인 집단같다....

 

이 문제를 처음 봤을 때는 브루트 포스를 이용해 문제를 풀어 정확도는 전부 맞았지만, 효율성에서 통과되지 않았다. 이 문제의 효율성 테스트를 통과하기 위해서는 누적합 알고리즘을 이용해야한다.

 

문제는 필자는 이 사실을 정말 알지도 못했기 때문에 긴 시간동안 풀지 못해 풀이를 설명하는 글을 참고했다. 1차원 배열의 누적합을 이용해 풀이해

 

[2, 3, 3, 1]의 배열에서 1번 인덱스 부터 2번 인덱스까지 2를 더해주고 싶다. 그 결과는 [2, 5, 5, 1]이 될 것이다. 이런 방식은 브루트 포스와 다르지 않다. 그렇다면 더 빠르게 더해주는 방법은 무엇일까?

 

위에서 설명 했듯이 누적합을 이용해주면 된다. 어떤 누적합이냐? 더해주는 값의 누적합이다. 위의 배열보다 길이가 1이 더 긴 새로운 배열을 0으로 채워주자 [0, 0, 0, 0, 0]. 그 다음 더하기를 시작하는 부분에는 더해주는 값을 더하고, 끝의 다음 부분에는 더해주는 값을 빼준다 [0, 2, 0, -2, 0]. 그 다음 왼쪽부터 누적합을 진행하면 [0, 2, 2, 0, 0]이 된다.

 

그렇다면 이러한 풀이 방식은 문제에 어디에 적용하는가? 바로 건물에게 주는 피해 혹은 회복량을 구하면 된다. 하지만, 그냥 단순하게 1차원 배열의 누적합을 구하면 효율성 테스트를 통과하지 못할 것이다. 이유는 1차원 배열을 구할 때 N이 된다면 누적합을 구하는 시간 복잡도가 O(NM)이 되기 때문이다.

 

자... 그러면 시간복잡도를 줄여보자. 1차원으로 구하던 누적합을 2차원적으로 생각해야한다.

[n, 0, 0, -n]

[0, 0, 0, 0]

[0, 0, 0, 0]

[-n, 0, 0, n]

처럼 0,0 부터 2,2 까지의 범위에 더해준다면 위의 2차원 배열처럼 새로운 배열을 만들어 주어야 한다. 그 다음 가로로 한번 세로로 한번 누적합을 구해야한다.

[n, n, n, 0]

[0, 0, 0, 0]

[0, 0, 0, 0]

[-n, -n, -n, 0]

가로로 한번 해주고

[n, n, n, 0]

[n, n, n, 0]

[n, n, n, 0]

[0, 0, 0, 0]

세로로 한던 더 해주면 이렇게 특정 범위에 n이라는 값을 더해줄 수 있다. 이러한 누적합을 2차원으로 구현해 적용해야 통과한다.

 

자 이제 누적합을 어떻게 사용해야하는지 잘 알게 되었을 것이다. 그렇다면 여러 피해 혹은 회복량을 정리할 수 있을 것이다. 모든 스킬들을 하나의 새로운 배열에 가로 세로 누적합을 하기 전의 단계를 진행해준다(피해량은 음수, 회복량은 양수). 모든 스킬들을 정리했다면 가로 세로 누적합을 진행해준다. 이렇게 구한 피해 및 회복량을 board에 더해주며 값을 도출할 수 있다.

 

이 참... 오랜만에 문제가 너무 어렵다는 느낌을 받았다.....

 

코드

function solution(board, skill) {
  const arr = Array.from({ length: board.length + 1 }, () => Array.from({ length: board[0].length + 1 }, () => 0));
    
  for (let [type, r1, c1, r2, c2, deg] of skill) {
    const t = type === 1 ? -1 : 1;
    arr[r1][c1] += (t * deg);
    arr[r2 + 1][c2 + 1] += (t * deg);
    arr[r1][c2 + 1] -= (t * deg);
    arr[r2 + 1][c1] -= (t * deg);
  }
    
  for (let i = 0; i < arr.length; i++) {
    for (let j = 1; j < arr[0].length; j++) {
      arr[i][j] += arr[i][j - 1];
    }
  }
  for (let i = 0; i < arr[0].length; i++) {
    for (let j = 1; j < arr.length; j++) {
      arr[j][i] += arr[j - 1][i];
    }
  }
    
  return board.reduce((acc, cur, idx) => acc + cur.filter((e, i) => e + arr[idx][i] > 0).length, 0);
}