파괴되지 않은 건물

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

프로그래머스

문제요약:

2차원 배열에서 사각형 범위만큼 특정숫자를 더하고 빼고를 주어진 리스트만큼 반복했을때, 모든 작업이 끝난 후 1이상인 값들의 갯수를 구하시오.

 

소요시간:

+A

난이도3

 

코딩:

def solution(board, skill):
    ch_t = {1:-1,2:1}
    temp = [[0]*(len(board[0])+1) for _ in range(len(board)+1)]
    #누적합 사용, 사각형의 시작지점에서 + 하고 끝에서 빼고 반대에선 다시더함
    for type,r1,c1,r2,c2,degree in skill:
        temp[r1][c1] += ch_t[type]*degree
        temp[r1][c2+1] -= ch_t[type]*degree
        temp[r2+1][c1] -= ch_t[type]*degree
        temp[r2+1][c2+1] += ch_t[type]*degree

    #가장자리 계산
    for x in range(len(board[0])):    
        temp[0][x+1] += temp[0][x] 
    for y in range(len(board)):    
        temp[y+1][0] += temp[y][0] 
    ans = 0

    for y in range(len(board)):
        for x in range(len(board[0])):
            temp[y+1][x+1] += temp[y+1][x] + temp[y][x+1] - temp[y][x]
            if temp[y][x]+board[y][x] >0:
                ans+=1
        
    return ans

사실 누적합이라는 개념을 몰랐는데 이문제는 효율성을 누적합을통해서만 해결할 수 있으므로, 누적합을 먼저 짧게소개하겠습니다. 

 

1차원을 먼저 예시로 들으면 어떤 배열이 있을 때 이 배열의 n길이 특정 구간의 합을 m 번 구하려면  O(m*n)의 시간복잡도를 가지게 됩니다. 하지만 이때 k+1번째 칸에 k를 더하는 연산을 전체다 해주게 되면, 각 칸은 0 부터 각칸까지의 합을 가지게 되는데 이때 원하는 구간의 끝값과 처음값-1 칸 값을 빼게 되면 특정구간의 합이 나오게 됨으로

ex) 1~6합 빼기 1~3합은 4~6합이됨. 그러므로 이때의 시간복잡도는 O(2*m)이 되게 됩니다. 

이를 또 이용하면 특정 구간에 특정값을 다 더하려한다면 시작지점에서 그값을 더한값을 기록하고, 그 끝나는 다음지점에서 뺀값을 기록한뒤, 앞에서 부터 누적합을 하면 역시 O(2*m)의 시간복잡도로 계산을 할 수 있게 됩니다..

 

이를 2차원에서도 역시 이용할 수 있는데, 특정 구간(2차원이기 때문에 사각형) 에서 시작지점에서 더한뒤 마주보는 꼭지점을 제외한 두곳에서는 빼주고 마주보는 꼭지점에서는 다시 더해준 뒤, 각각 인덱스가 0 인지점들은 미리 누적합을 해주고, 그후 순서대로 위값과 왼쪽값을 더하고 그 후 왼쪽위값을 빼주면 계산이 완료됩니다.