[Programmers] 파괴되지 않은 건물 - swift (Level 3)

문제

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

프로그래머스

문제 요약

건물들의 내구도가 2차원 배열로 주어지고 이 건물에 공격과 회복 스킬을 쓸 수 있습니다. 

건물 내구도 2차원배열임다

공격은 내구도를 감소시키고 회복은 내구도를 증가시킵니다. 공격 스킬과 회복 스킬은 (r1, c1) ~ (r2, c2) 사이 범위 내 건물에 적용됩니다. 공격과 회복이 배열로 주어지고 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 구하는 문제입니다.

풀이

2차원 누적합을 구하는 문제입니다. 단순 구현을 하게될 경우 O(N*M*Skill 개수)만큼의 시간이 들기 때문에 효율성 테스트를 통과할 수 없습니다. 2차원 누적합을 구하는 방법을 응용해야 합니다. (r1, c1) ~ (r2, c2) 범위에서 공격과 회복 스킬이 주어졌다면 그 범위 내의 숫자들에만 누적이 되어야 합니다. 

 

2차원 배열을 조금 축소시켜 3x3 2차원 배열에서 (0, 0) ~ (1, 1)을 N만큼 증가시키는 경우를 생각해봅니다.

 

초반 누적합 2차원 배열은 아래와 같습니다. 

0 0 0 
0 0 0
0 0 0 

N만큼 증가시켰을 경우 아래처럼 생각할 수 있습니다. 

누적 배열:
N 0 -N
0 0 0 
-N 0 N 

실제 배열:
N N 0 
N N 0 
0 0 0

(r1, c1) ~ (r2, c2) 범위 인 경우 아래 4개의 좌표만 수정하면 되기 때문에 시간 복잡도는 O(N*M)에서 O(1)로 단축시킬 수 있습니다. 

(r1, c1)
(r2+1, c1)
(r1, c2+1)
(r2+1, c2+1)

코드

 

 

cf> 1차원 누적합 

1차원 누적합

2차원 누적합은 열과 행을 전부 누적하는 것이고 1차원은 단순 행만 누적하면 됩니다. 

누적 배열 : N 0 0 0 0 0 -N
실제 배열 : N N N N N N 0