[프로그래머스] Lv.3 파괴되지 않은 건물 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/92344
• 2022 KAKAO BLIND RECRUITMENT 문제
• 🔑 : 누적합
• skill 리스트마다 board의 값을 바꿔주고 마지막에 1보다 큰 것의 개수를 세니 당연히 시간초과남
• board 보다 1열 1행 큰 map을 만들어주고 skill 하나에 점 4개만 찍고 난 후 누적 합을 계산

 

def solution(board, skill):
    answer = 0
    n, m = len(board), len(board[0])
    map = [[0] * (m+1) for _ in range(n+1)] # board 보다 1열 1행 큰 맵

    for type, r1, c1, r2, c2, degree in skill:
        if type == 1: degree *= -1

        map[r1][c1] += degree   # 왼쪽 위
        map[r1][c2+1] -= degree # 오른쪽 위
        map[r2+1][c1] -= degree # 왼쪽 아래
        map[r2+1][c2+1] += degree  # 오른쪽 아래


    for i in range(n):
        for j in range(m):  
            map[i][j+1] += map[i][j]  # x 축으로 값을 누적

            if i > 0: # 두 번째 행 부터는  
                map[i][j] += map[i-1][j]  # y 축으로도 값을 누적
    
            if board[i][j] + map[i][j] > 0: # 보드와 누적 합 계산
                answer += 1

    return answer