링크
https://school.programmers.co.kr/learn/courses/30/lessons/92344
문제
N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.
제한사항
- 1 ≤ board의 행의 길이 (= N) ≤ 1,000
- 1 ≤ board의 열의 길이 (= M) ≤ 1,000
- 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
- 1 ≤ skill의 행의 길이 ≤ 250,000
- skill의 열의 길이 = 6
- skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
- type은 1 혹은 2입니다.
- type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
- type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
- (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
- 0 ≤ r1 ≤ r2 < board의 행의 길이
- 0 ≤ c1 ≤ c2 < board의 열의 길이
- 1 ≤ degree ≤ 500
- type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
- type이 2이면 degree만큼 건물의 내구도를 높입니다.
- 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.
정확성 테스트 케이스 제한 사항
- 1 ≤ board의 행의 길이 (= N) ≤ 100
- 1 ≤ board의 열의 길이 (= M) ≤ 100
- 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
- 1 ≤ skill의 행의 길이 ≤ 100
- 1 ≤ degree ≤ 100
문제 풀이
효율성 테스트가 존재하지 않는다면 이 문제는 간단하게 이차원 배열에서 해당 되는 부분에 degree의 값만큼 +, -를 하면 간단하게 해결되는 문제이다. 하지만 문제의 제한 사항에서 최대로 오래 걸리게 되는 경우를 생각했을 때 1000 1000 250,000의 값으로 250,000,000,000(2500억)의 연산에 걸려 시간초과를 발생시킨다.
따라서 이 문제는 시간복잡도를 간단하게 만드는 것이 관건이다.
예를 들어 0으로 채워진 4*4의 배열이 있을 때 (0, 0) ~ (2, 2)에 4만큼의 데미지를 준다고하면 다음과 같이 나타낼 것이다.
-4 -4 -4 0
-4 -4 -4 0
-4 -4 -4 0
0 0 0 0
이런식으로 나타낼 수도 있겠지만 누적합의 개념을 적용시켜서 나타내면 다음과 같이 나타낼 수 있다.
-4 0 0 4
0 0 0 0
0 0 0 0
4 0 0 -4
이렇게만 보면 두 배열의 관계를 알아차리기 어려운데 실제로 누적합으로 배열의 원소들을 더해보면 아래의 배열이 위의 배열과 같아지는 것을 확인할 수 있다.
- 왼쪽에서 오른쪽으로 각각의 원소들을 더하기
-4 -4 -4 0
0 0 0 0
0 0 0 0
4 4 4 0 - 위에서 아래로 각각의 원소들을 더하기
-4 -4 -4 0
-4 -4 -4 0
-4 -4 -4 0
0 0 0 0
실제로 더해보면 같은 것을 알 수가 있다.
위의 내용을 식으로 정리하면 다음과 같다
(x1, y1) = n
(x2+1, y1) = -n
(x1, y2+1) = -n
(x2+1, y2+1) = n
단, 주의할 점으로 x + 1과 y + 1이 원래 board 배열을 넘어가는 경우에는 해당 누적을 적용하지 않는다는 것을 염두하고 코드를 작성한다.
skill이 여러 개일 경우에 누적합 배열로 만들고 다음 skill에 대해서 다시 누적합 배열을 적용하고 마지막에 한꺼번에 배열의 원소들을 더하는 식으로 코드를 작성한다.
이렇게 skill 하나에 대해서 4번의 접근 및 값 변경, 누적합을 구하기 위해서 전체 배열 사이즈만큼 2회 반복, 원래의 배열에 누적합 배열을 더하는 작업으로 시간을 대폭 단축시키는 것이 가능하다.
코드
// board : 건물의 내구도를 나타내는 2차원 정수 배열
// skill : [type, r1, c1, r2, c2, degree]
// type : 1이면 공격, 2면 회복
// (r1, c1)부터 (r2, c2) 까지 공격 혹은 회복
// degree : 해당 수치만큼 공격 혹은 회복
function solution(board, skill) {
let r = board.length
let c = board[0].length
// 깊은 복사 걸려서 각각의 이차원들이 연동됨
// let accBoard = new Array(r).fill(new Array(c).fill(0))
let accBoard = new Array(r).fill(0).map(e => new Array(c).fill(0))
skill.map(el => {
const [type, r1, c1, r2, c2, degree] = el
// 공격과 회복의 경우로 나눠서 작업
switch(type) {
case 1:
accBoard[r1][c1] = accBoard[r1][c1] - degree
if(r2 + 1 < r) accBoard[r2 + 1][c1] = accBoard[r2 + 1][c1] + degree
if(c2 + 1 < c) accBoard[r1][c2 + 1] = accBoard[r1][c2 + 1] + degree
if(r2 + 1 < r && c2 + 1 < c) accBoard[r2 + 1][c2 + 1] = accBoard[r2 + 1][c2 + 1] - degree
break
case 2:
accBoard[r1][c1] = accBoard[r1][c1] + degree
if(r2 + 1 < r) accBoard[r2 + 1][c1] = accBoard[r2 + 1][c1] - degree
if(c2 + 1 < c) accBoard[r1][c2 + 1] = accBoard[r1][c2 + 1] - degree
if(r2 + 1 < r && c2 + 1 < c) accBoard[r2 + 1][c2 + 1] = accBoard[r2 + 1][c2 + 1] + degree
break
}
})
// 가로로 누적합 계산
for(let i = 0; i < r; i++) {
for(let j = 0; j < c - 1; j++) {
accBoard[i][j + 1] += accBoard[i][j]
}
}
// 세로로 누적합 계산
for(let i = 0; i < c; i++) {
for(let j = 0; j < r - 1; j++) {
accBoard[j + 1][i] += accBoard[j][i]
}
}
// board 배열과 계산된 누적합 배열 합산
for(let i = 0; i < r; i++) {
for(let j = 0; j < c; j++) {
board[i][j] += accBoard[i][j]
}
}
return board.flat().filter(el => el > 0).length
}
```- 