2022 카카오 파괴되지않은 건물

파괴되지않은 건물 프로그래머스 문제 링크

풀기 전에 알아야할 알고리즘

- 누적 합 (Prefix_sum)

출처: https://en.wikipedia.org/wiki/Prefix_sum

누적 합은 배열에서 구간의 합을 prefix sum을 이용해 상수시간에 구하는 알고리즘이다.
누적 합에서 배열의 [L, R] 구간의 합은 prefix[R] - prefix[L-1]이다.

아이디어가 필요한 이유

skill의 최대 개수가 250,000이기 때문에 skill을 iterate할 때
skill 범위를 이중 for문으로 표시하면 시간 초과가 난다.

아이디어

먼저 1차원으로 축소하여 생각하였을 때, [1, 4]에 데미지 2를 주는 아이디어는 다음과 같다.

1. 새로운 배열을 만든다. [0 for _ in range(n+1)]
   • n+1인 이유는 접두사 합을 이용하기 위함이다.
2. [ 0, -2, 0, 0, 0, 2, ... ]
3. 접두사 합으로 만들면 [ 0, -2, -2, -2, -2, 0 ] 이 된다.
4. 이를 원본 배열과 더해주면 결과적으로 [1, 4]에 데미지 2를 준 것과 같다.

2차원으로 확장

행과 열을 분리하여 새 배열에 표시하고, 순서대로 누적합을 적용해본다.

:: 행과 열을 따로 배열에 표시하였기 때문에 행과 열의 누적합을 동시에 진행할 수 없다.

def solution(board, skill):
    n = len(board)
    m = len(board[0])
    dmg_board = [[0 for _ in range(m+1)] for _ in range(n+1)]
    answer = n * m
    for s in skill:
        tp, r1, c1, r2, c2, degree = s
        tp = 1 if tp == 2 else -1

        degree *= tp
        dmg_board[r1][c1] += degree
        dmg_board[r1][c2+1] += degree * -1
        dmg_board[r2+1][c1] += degree * -1
        dmg_board[r2+1][c2+1] += degree
        
#x
    for y in range(n + 1):
        for x in range(m + 1):
            if x-1 >= 0:
                dmg_board[y][x] += dmg_board[y][x - 1]

#y
    for y in range(n + 1):
        for x in range(m + 1):
            if y - 1 >= 0:
                dmg_board[y][x] += dmg_board[y - 1][x]

                
    for y in range(n):
        for x in range(m):
            board[y][x] += dmg_board[y][x]
    for y in range(n):
        for x in range(m):
            if board[y][x] <= 0:
                answer -= 1
    return answer
# -2 0 2 0
# 0 -4 0 4
# 2 0 -2 0
# 0 4 0 -4

# -2 -2 0 0
# 0 -4 -4 0
# 2 2 0 0
# 0 4 4 0

# -2 -2 0 0
# -2 -6 -4 0
# 0 -4 -4 0
# 0 0 0 0