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

문제

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

프로그래머스

 

풀이

이 문제는 쉬워보이지만 효율성 테스트를 통과하기 어려운 문제입니다.

 

호율성 테스트 실패 코드

def solution(board, skill):
    n = len(board)
    m = len(board[0])
    answer = n * m
    
    for type, r1, c1, r2, c2, degree in skill:
        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                if type == 1:
                    if 0 < board[i][j] <= degree:
                        answer -= 1
                    board[i][j] -= degree
                else:
                    if -degree < board[i][j] <= 0:
                        answer += 1
                    board[i][j] += degree
            
    return answer

위 코드는 틀린 코드는 아니지만 2차원 배열의 원소를 일일이 참조하기 때문에 시간 복잡도가 O(N*M)이 됩니다. 따라서 효율성 테스트는 통과할 수 없습니다.

 

효율성 테스트 통과 방법

시간 복잡도가 O(N*M)이기 때문에 이를 O(N) 혹은 O(1)로 줄여야 합니다.

이때 누적합을 이용하면 시간 복잡도를 줄일 수 있습니다. 2차원 배열의 누적합을 이해하기 위해 우선 1차원 배열의 누적합을 예로 들어보겠습니다.

길이가 5인 배열에서 0 ~ 2번째까지 N만큼 감소시키고 싶은 경우에 다음과 같이 새로운 배열을 만듭니다. N이 2번째가 아닌 3번째 인덱스에 할당된 것을 주의해주세요.

[-N, 0, 0, N, 0, 0]

위의 배열을 0번째부터 마지막 인덱스까지 누적합을 하게 되면 다음과 같습니다.

[-N, -N, -N, 0, 0, 0]

0~2번째 인덱스 원소가 -N이 되어 기존의 배열과 위 배열을 합하게 되면 0~2번째 원소를 N만큼 감소시킬 수 있습니다.

이것이 누적합을 이용한 방법입니다.

1차원 배열의 원소를 계속 참조하여 더하는 경우 O(N)의 시간 복잡도를 가집니다. 하지만 누적합 방식으로 구현하게 되면 누적합을 기록하는 배열에 값을 저장한 후 마지막에 한 번만 누적합을 계산하여 기존 배열과 더하면 되므로 O(1)의 시간 복잡도를 가집니다.

 

2차원 배열을 누적합하는 절차는 다음과 같습니다.

2차원 배열 또한 마찬가지로 누적합 범위를 기록한 후 한 번만 누적합을 진행하기 때문에 O(1)의 시간 복잡도를 가집니다.

 

코드

파이썬

def solution(board, skill):
    answer = 0
    n = len(board)
    m = len(board[0])
    tmp = [[0] * (m+1) for _ in range(n+1)]
    
    for type, r1, c1, r2, c2, degree in skill:
        tmp[r1][c1] += -degree if type == 1 else degree
        tmp[r1][c2+1] += degree if type == 1 else -degree
        tmp[r2+1][c1] += degree if type == 1 else -degree
        tmp[r2+1][c2+1] += -degree if type == 1 else degree
        
    for i in range(n):
        for j in range(m-1):
            tmp[i][j+1] += tmp[i][j]
            
    for i in range(m):
        for j in range(n-1):
            tmp[j+1][i] += tmp[j][i]
            
    for i in range(n):
        for j in range(m):
            board[i][j] += tmp[i][j]
            if board[i][j] > 0:
                answer += 1
            
    return answer