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

🔗 링크

---

 

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

 

 

🔒 문제 

---

🔎 문제풀이

---

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

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

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

 

skill을 다 계산한 배열의 값은

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

# 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

👨🏻‍💻 코드

---

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