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

https://programmers.co.kr/learn/courses/30/lessons/92344

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

 

문제를 풀었을 때, 누적 합을 생각했으나 시간초과가 났다.

당시에 풀었던 방법은 

예를 들어, skill이 [1, 0, 0, 3, 4, 4] 라고 한다면, 

-4 0 0 0 0 4

-4 0 0 0 0 4

-4 0 0 0 0 4

로 행마다 값을 주어 누적 합을 계산하였다.

 

더 빠른 방법을 생각해보니 밑에 행을 추가하여,

-4 0 0 0 0 4

0 0 0 0 0 0

0 0 0 0 0 0

4 0 0 0 0 -4

로 값을 주고 열 방향으로 누적 합을 한 뒤, 행 방향으로 누적 합을 계산하면 위의 결과과 같고 더 빠르게 구할 수 있어 이처럼 진행하여 풀었다.

 

def solution(board, skill):
    answer = 0
    
    m = [[0] * (len(board[0]) + 1) for i in range(len(board) + 1)]
    
    for ty, i1, j1, i2, j2, da in skill:
        if ty == 1: da = -1 * da
        
        m[i1][j1] += da
        m[i1][j2+1] += -1 * da
        m[i2+1][j1] += -1 * da
        m[i2+1][j2+1] += da
        
    for i in range(len(board)):
        for j in range(len(board[0])):
            m[i][j+1] += m[i][j]
        
            if i > 0:
                m[i][j] += m[i-1][j]
            
            if board[i][j] + m[i][j] > 0: answer += 1  
    
    return answer

print(solution([[5, 5, 5, 5, 5], [5, 5, 5, 5, 5], [5, 5, 5, 5, 5], [5, 5, 5, 5, 5]], [[1, 0, 0, 3, 4, 4], [1, 2, 0, 2, 3, 2], [2, 1, 0, 3, 1, 2], [1, 0, 1, 3, 3, 1]])) # 10