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

풀이

누적합을 이용해 skill을 O(n2)으로 줄여야 한다. 

오랜 시간 동안 고민했던 것은 2차원 배열에서 누적 합을 어떻게 풀어야 할지 고민을 했다.

2차원 누적 합의 공식은 각 row를 먼저 다 누적해서 더한 후 col을 누적해서 더해주면 된다. 

---

초기 배열

-2	0	2
0	0	0 map[2][3])
2	0	-2 map[3][3]

---

누적합 배열

-2	-2  (psum[1][2])	0  (psum[1][3])
-2	-2  (psum[2][2])	0 ( psum[2][3])
0	0	0

 

잘 생각하면 psum[2][3] 을 계산하면 map[2][3] + psum[1][3] + psum[2][2] -psum [1][2]의 경우는 변화량이 한번 제거된다.하지만 map[3][3]의 경우에는 변화량이 두 번 제거가 됨으로 복원 작업이 필요하다.

코드

def make_psum(board):
    psum = [[0] * len(board[0]) for _ in range(len(board))]
    psum[0][0] = board[0][0]

    #첫 row
    for i in range(1, len(board[0])):
        psum[0][i] = board[0][i] + psum[0][i - 1]

    #첫 col
    for i in range(1, len(board)):
        psum[i][0] = board[i][0] + psum[i - 1][0]

    
    for i in range(1, len(board)):
        for j in range(1, len(board[0])):
            psum[i][j] = board[i][j] + psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1]

    return psum

def solution(board, skills):
    answer = 0

    skills_board = [[0] * len(board[0]) for _ in range(len(board))]

    for skill in skills:
        type, row_x, row_y, col_x, col_y, deg = skill

        if type == 1:
            deg = -deg

        skills_board[row_x][row_y] += deg

        if col_x + 1 < len(board):
            skills_board[col_x + 1][row_y] += (-deg)

        if col_y + 1 < len(board[0]):
            skills_board[row_x][col_y + 1] += (-deg)

        
        if col_x + 1 < len(board) and col_y + 1 < len(board[0]):
            skills_board[col_x + 1][col_y + 1] += (deg)

    psum_skill_board = make_psum(skills_board)
        
    answer = 0

    for row in range(len(board)):
        for col in range(len(board[0])):
            board[row][col] += psum_skill_board[row][col]

            if board[row][col] > 0:
                answer += 1
    
    return answer


if __name__ == "__main__":
    board = [[1,2,3],[4,5,6],[7,8,9]]
    skill = [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]

    solution(board, skill)

 

소감

누적합 문제인지는 알았지만 어떻게 적용해야 할지 몰라서 감을 못 잡고 있었다. 풀이를 검색하던 중 태상이의 훈련소 생활을 풀고 오라는 추천을 받았다. 해당 문제를 풀고 오니 바로 풀 수 있었다. 

디버깅에 시간이 걸렸는데 디버깅을 어떻게 하면 작게 할 수 있는지 생각해보자.

 

 

문제 링크

파괴되지 않는 건물