[파이썬][프로그래머스] 파괴되지 않은 건물

🔗 링크

---

 

코딩테스트 연습 - 파괴되지 않은 건물

 

 

🔒 문제 

---

🔎 문제풀이

---

 처음에는 skill에 있는 좌표 모든 곳을 type에 맞게 계산을 해서 풀었었다. 당연히 효율성에서 시간 초과가 났었다.
좌표를 기억 표시해두고 한 번에 모든 걸 계산할 수 있는 방법을 찾아야 했었다. 누적합을 사용하여 풀어보았다.

 첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 표시를 해주었다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 표시

 

skill을 다 계산한 배열의 값은

마지막으로 모든 y축에 대한 x축 부분합과 x축에 대한 y축 부분합을 구한 후 보드의 값과 배열의 값을 더해서 0보다 크면 정답을 늘려주는 식으로 풀었다.

python

닫기 줄바꿈

# R, C = len(board), len(board[0]) 보드 크기
# mat = [[0] * (C + 1) for _ in range(R + 1)] 좌표에 따라 degree값 저장한 배열

for r in range(0, R + 1):
​​​​​​​​for c in range(1, C + 1):
​​​​​​​​​​​​mat[r][c] += mat[r][c - 1]

for c in range(0, C + 1):
​​​​for r in range(1, R + 1):
​​​​​​​​mat[r][c] += mat[r - 1][c]

for r in range(R):
​​​​for c in range(C):
​​​​​​​​board[r][c] += mat[r][c]
​​​​​​​​if board[r][c] > 0:
​​​​​​​​​​​​answer += 1

👨🏻‍💻 코드

---

python

닫기 줄바꿈

def solution(board, skill):
​​​​answer = 0
​​​​R, C = len(board), len(board[0])
​​​​mat = [[0] * (C + 1) for _ in range(R + 1)]

​​​​for s in skill:
​​​​​​​​type, r1, c1, r2, c2, degree = map(int, s)
​​​​​​​​if type == 1:
​​​​​​​​​​​​mat[r1][c1] -= degree
​​​​​​​​​​​​mat[r2 + 1][c2 + 1] -= degree
​​​​​​​​​​​​mat[r1][c2 + 1] += degree
​​​​​​​​​​​​mat[r2 + 1][c1] += degree

​​​​​​​​else:
​​​​​​​​​​​​mat[r1][c1] += degree
​​​​​​​​​​​​mat[r2 + 1][c2 + 1] += degree
​​​​​​​​​​​​mat[r1][c2 + 1] -= degree
​​​​​​​​​​​​mat[r2 + 1][c1] -= degree

​​​​for r in range(0, R + 1):
​​​​​​​​for c in range(1, C + 1):
​​​​​​​​​​​​mat[r][c] += mat[r][c - 1]

​​​​for c in range(0, C + 1):
​​​​​​​​for r in range(1, R + 1):
​​​​​​​​​​​​mat[r][c] += mat[r - 1][c]

​​​​for r in range(R):
​​​​​​​​for c in range(C):
​​​​​​​​​​​​board[r][c] += mat[r][c]
​​​​​​​​​​​​if board[r][c] > 0:
​​​​​​​​​​​​​​​​answer += 1

​​​​return answer