[プログラマーLv 3.]未破壊の建物(Python)

1.質問

問題の説明

せいげんじょうけん

にゅうしゅつりょく

2.解法

私が考えている過程

コード#コード#

def solution(board, skill):
    answer = 0

    for type, r1, c1, r2, c2, degree in skill:
        for x in range(r1, r2+1):
            for y in range(c1, c2+1):
                if type == 1:
                    board[x][y] -= degree
                else:
                    board[x][y] += degree

    # 2차원 배열의 원소를 일일이 참조하기 때문에 시간 복잡도가 O(N*M)
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] > 0:
                answer += 1
    return answer

累計和の最終コードの使用

def solution(board, skill):
    answer = 0
    temp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]  # 누적합을 위한 판

    # 누적합을 위한 세팅
    for type, r1, c1, r2, c2, degree in skill:
        if type == 1:
            temp[r1][c1] += -degree
            temp[r1][c2 + 1] += degree
            temp[r2 + 1][c1] += degree
            temp[r2 + 1][c2 + 1] += -degree
        else:
            temp[r1][c1] += degree
            temp[r1][c2 + 1] += -degree
            temp[r2 + 1][c1] += -degree
            temp[r2 + 1][c2 + 1] += degree

    # 행 누적합
    for x in range(len(temp) - 1):
        for y in range(len(temp[0]) - 1):
            temp[x][y + 1] += temp[x][y]

    # 열 누적합
    for x in range(len(temp) - 1):
        for y in range(len(temp[0]) - 1):
            temp[x + 1][y] += temp[x][y]

    # 값 확인
    for x in range(len(board)):
        for y in range(len(board[0])):
            board[x][y] += temp[x][y]
            if board[x][y] > 0:
                answer += 1

    return answer