[프로그래머스] 92344 파괴되지 않는 건물 2022 KAKAO BLIND RECRUITMENT

def solution(board, skill):
    answer = 0
    N = len(board)
    M = len(board[0])
    skill_board = [[0 for i in range(M+2)] for _ in range(N+2)]
    cnt = 0
    for sk in skill:
        sk_type, r1,c1,r2,c2 ,degree = sk
        if sk_type == 1:
            degree = -degree
        r1 +=1; r2+=1; c1+=1; c2+=1
        skill_board[r1][c1] += degree
        skill_board[r1][c2+1] -= degree
        skill_board[r2+1][c1] -= degree
        skill_board[r2+1][c2+1] += degree
    for x in range(1,N+1):
        for y in range(1,M+1):
            skill_board[x][y] = skill_board[x][y] + skill_board[x-1][y] + skill_board[x][y-1] - skill_board[x-1][y-1]
    for x in range(N):
        for y in range(M):
            if board[x][y] +skill_board[x+1][y+1] >0:
                answer += 1
    return answer

이 문제도 실전에서 풀지 못했던 문제였다.

 

7번 문제에 너무 힘을 쏟은 나머지, 마지막 20분동안 풀다가 범위 측정을 제대로 못해서, 풀지 못한 문제였다.

 

평소 2차원 누적합을 잘 다루지 않다보니, 범위를 구하는데 실수를 했고, 그 범위의 누적합을 구하는데 연산을 실후 했다.

 

이 문제에서 중요한 것은 폭발 범위에 맞춰서 누적합을 할 수 있게, 숫자들을 정리해 놓고, 누적합을 구하면 되는 문제이다.

 

폭발이 시작하는 r1,c1에는 +degree을 해주고,

 

폭발이 끝나는 위치인 r2+1,c1 , r1,c2+1에는 -degree을 해준다.

 

그리고 중요한 것은 r2+1, c2+1 에서는 +degree를 해주는 것이다.

 

이 누적합을 마킹해놓은 상태에서 가로로 1번 누적합 세로로 1번 누적합을 진행을 한다고 생각을 해보면, 왜 그 위치에서 마킹을 해줘야하는지 이해할 수 있다.

 

이 문제는 누적합이라는 접근까지 했지만, 디버깅 할 시간이 부족해 풀지 못했던 아쉬웠던 문제였다..

 

2차원 누적합은 매번 풀때마다, 햇갈려하는 유형이기 때문에 좀 더 연습해야겠다.