[Python 문제풀이] 프로그래머스 '파괴되지 않은 건물'

Programmers Lv.3 파괴되지 않은 건물 파이썬 문제풀이

누적합 (Prefix Sum) 설명

조건파악

board의 크기 최대 (1,000 x 1,000)

skill의 길이 최대 (250,000)

 

얼핏 보면 상당히 쉬운 문제이지만 효율성 테스트를 통과하기 어렵다. 단순한 알고리즘을 이용할 경우 최악의 경우 board에 있는 모든 원소인 1,000,000개에 대해 250,000번 연산을 수행해야 한다. 따라서 N은 최대 250,000,000,000이므로 O(N*M)의 방법으로는 도저히 풀 수 없게 된다.

접근

 스킬들에 따른 영향을 사전에 모두 계산해놓은 뒤, board에 한 번에 합산한다.

 board의 원소 수를 N, skill의 길이를 M이라 하자. 이 경우 수행되는 연산의 수는 대략 k*M + N이다.(k는 임의의 가중치) 즉 시간복잡도 O(N)을 가진다. 해당 부분을 염두에 두고 어떻게 skill을 사전에 계산해놓을지 생각해보자.

 

1. 2차원 누적합 A배열 만들기

 

그림 2

여러 데이터에 일관적인 연산을 할 때 누적합이라는 방법을 사용한다. 위와 같이 3개의 데이터에 X를 일괄적으로 더한다는 경우, 크기가 똑같은 임의의 배열을 만들어 데이터의 위치 양끝에 표시를 해놓는다. 그러고 나서 인덱스를 순차적으로 읽으며 누적시키면 뒤이어 오는 모든 데이터에 누적값을 전파시킬 수 있다.

 

그림 3

 그림 3은 그림 2의 1차원 배열을 여러개 이어붙여 만든 2차원 배열이다. 각 행에 대해 누적합을 수행하면 같은 결과가 만들어질 것이 예상된다. 그럼 이번엔 이 2차원 배열을 다시 누적합을 통해 만들 방법을 생각해보자.

 

그림 4

 그림 4를 보면 빨간 화살표를 따라 누적합을 수행할 경우 그림 3이 만들어짐을 알 수 있다. 이것으로 최종적인 2차원에서 특정 사각형 범위에 일괄적인 연산을 하기 위한 누적합 배열이 만들어졌다.

 

2. 서로 다른 연산은 독립적이다

 

 문제는 skill이 두 개 이상일 경우 A행렬 하나에 모든 데이터를 넣어도 되는지 확인할 필요가 있다. 그러기 위해서는 각 연산이 독립적이어서 순서가 바뀌어도 결과가 똑같아야 한다. skill은 각 데이터에 +- 합 연산이고 누적합 방법 역시 +- 합 연산만 이용한다. 따라서 결론적으로 각 연산은 독립적이므로 skill을 모두 누적합 A로 만들어 놓고 한 번에 계산해도 무방하다.

 

의사코드

누적합 A행렬이 될 attack배열을 만듦

skill에 대해 반복하며 attack에 데이터를 기록

attack에 대해 행을 따라 누적합 수행

attack에 대해 열을 따라 누적합 수행

board과 attack을 합하며 음수가 되는 원소의 수를 카운트 -> 정답

 

구현

def solution(board, skill) :
    result = 0
    m = len(board[0])
    n = len(board)
    attack = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for sign, r1, c1, r2, c2, amount in skill :
        deal = amount if sign == 2 else -amount
        attack[r1][c1] += deal
        attack[r1][c2+1] -= deal
        attack[r2+1][c1] -= deal
        attack[r2+1][c2+1] += deal
    for i in range(n) :
        for j in range(m) :
            attack[i][j+1] += attack[i][j]
    for j in range(m) :
        for i in range(n) :
            attack[i+1][j] += attack[i][j]
    for i in range(n) :
        for j in range(m) :
            board[i][j] += attack[i][j]
            if board[i][j] > 0 :
                result += 1
    return result