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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

일반적으로 skill이 적용되어야 하는 범위에 매번 (r1, c1) ~ (r2, c2)에 적용을 하면 최악의 경우 O(Skill의 개수 * 최대 가로 길이 * 최대 세로 길이) = O(250000 * 1000 * 1000)가 되어 시간 초과가 나게 됩니다. 

 

매번 범위에 적용하지 않고 한번에 발생한 Skill을 적용하기 위하여 누적합 방식이 필요합니다. 

1차원 배열을 기준으로 생각했을 때 1 ~ 3범위에 적이 2만큼의 스킬을 사용했다고 가정하면 아래와 같이 시작 인덱스에 -2를 적용해주고 (범위의 끝 + 1) = (3 + 1)에는 다시 +2를 세팅해주면 됩니다.

prefix_sum = [0, -2, 0, 0, 2, 0]

다음으로 누적합을 진행하면 아래와 같이 1 ~ 3 범위에 적이 사용한 2만큼의 스킬이 적용된 것을 확인할 수 있습니다.

prefix_sum = [0, -2, -2, -2, 0, 0]

 

2차원 배열도 크게 다르지 않습니다. 적이 (1, 1) ~ (2, 2)에 스킬을 사용하면 (1, 1) =  -2, 가로 범위(1, 3)의 끝에는  2, 세로 범위 (3, 1) 의 끝에는 2, 대각선 (3, 3) 범위 끝에는 -2를 세팅해주면 됩니다. 

prefix_sum = [ 0, -2, 0,  2, 0
               0,  0, 0,  0, 0
               0,  2, 0, -2, 0 ]

이 상태에서 2차원 누적합을 적용하게 되면 아래와 같이 범위에 스킬이 적용된 것을 확인할 수 있습니다. 

prefix_sum = [ 0, -2, -2, 0, 0
               0, -2, -2, 0, 0
               0,  0,  0, 0, 0 ]

 

이런 방식을 사용하면 prefix_sum의 세팅하는데 O(1)이 걸리고 누적합 O(N * N)을 적용하고 파괴되지 않은 건물을 확인하는데 O(N * N)이 걸리므로 O(N * N)만에 해결할 수 있습니다.

# 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344
ENEMY = 1
FRIEND = 2

def solution(board, skill):
    answer = 0
    row = len(board)
    col = len(board[0])

    prefix_sum = [
        [0] * (col + 2)
        for _ in range(row + 2)
    ]

    for type, r1, c1, r2, c2, degree in skill:
        prefix_sum[r1 + 1][c1 + 1] += degree if type == FRIEND else -degree
        prefix_sum[r2 + 2][c1 + 1] -= degree if type == FRIEND else -degree
        prefix_sum[r1 + 1][c2 + 2] -= degree if type == FRIEND else -degree
        prefix_sum[r2 + 2][c2 + 2] += degree if type == FRIEND else -degree

    for i in range(1, row + 2):
        for j in range(1, col + 2):
            prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1] + prefix_sum[i][j]

    for i in range(row):
        for j in range(col):
            board[i][j] += prefix_sum[i + 1][j + 1]
            if board[i][j] > 0:
                answer += 1

    return answer

위 코드에서 유의해야할 점은 prefix_sum을 계산하기 위해 행과 열을 2개씩 추가해두었습니다. 그래서 board의 (0, 0) -> prefix_sum의 (1, 1)에 대응되게 됩니다. 행과 열을 하나씩 추가한 이유는 prefix_sum을 계산할 때 i, j가 0인 경우 i -1, j - 1에서 에러가 발생할 수 있으므로 하나씩 추가였고 스킬의 적용범위에 행과 열의 마지막 인덱스가 포함된 경우 누적합을 위해 (범위의 끝 + 1)에 접근하는 경우 에러가 발생할 수 있어서 하나씩 추가하여 총 2개씩 추가하게 되었습니다.