[프로그래머스 Lv3.] 파괴되지 않은 건물(python)

1. 문제

문제 설명

제한사항

입출력

2. 풀이 과정

내가 생각한 진행 과정

• board를 돌면서 type에 따른 degree를 더하고 빼기 -> 효율성 통과X

코드

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

• 시간 복잡도가 O(N*M)이기 때문에 이를 O(N) 혹은 O(1)로 줄여야함

누적합을 이용한 최종코드

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