[프로그래머스] Lv3. 파괴되지 않은 건물 (2022 카카오 공채)

🔗

풀이

❌ 일반 완전탐색

1000x1000 배열에 연산의 최대 횟수가 25만이다.

def solution(board, skill):    
    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:
                    board[i][j] -= degree
                elif _type == 2:
                    board[i][j] += degree
                    
    ans = 0
    for row in board:
        ans += sum(1 for x in row if x > 0)
            
    return ans

🫠 1차원 배열로 바꾼 후 누적합

1차원 배열로 바꿔준 다음에 누적합을 구해봤지만 여전히...
25만번의 매 연산마다 행의 개수만큼 돌아가기 때문에 만약 매번 행의 크기가 1000이라면 2천만의 연산이 수행될 수 있다

def solution(board, skill):
    def index(x, y):
        return x*m+y
    
    def prefix_sum(start, end, degree):
        attack[start] += degree
        attack[end] -= degree
        
    n, m = len(board), len(board[0])
    attack = [0]*(m*n+1)
    _board = []
    for row in board:
        _board.extend(row)
    
    for ty, r1, c1, r2, c2, degree in skill:
        if ty == 1:
            degree *= -1
            
        for x in range(r1, r2+1):
            start, end = index(x, c1), index(x, c2+1)
            prefix_sum(start, end, degree)
    
    _board[0] += attack[0]
    ans = _board[0] > 0
    for i in range(1, len(attack)-1):
        attack[i] += attack[i-1]
        _board[i] += attack[i]
        if _board[i] > 0:
            ans += 1
        
    return ans

😇 2차원 누적합

이 블로그를 참고했다.

2차원 누적합은 어떻게 하는건지 모르겠어서 1차원으로 풀었는데 2차원 누적합이 되는거였다.

2차원이기 때문에 각 꼭지점에 위치하는 부분에 더하거나 빼야 할 숫자를 누적해서 더해준다. 먼저 시작점이 되는 (r1, c1) 부분은 누적할 합 숫자를 더해준다. 이 부분에서 행, 열로 이동하게 된다. (r1, c2+1) 부터는 이 숫자가 누적되면 안 된다. 여기서는 숫자를 빼준다. 그럼 누적합이 0이 된다.

행 r2까지는 누적합이 수행되어야 한다. 하지만 (r2+1, c1)부터는 누적되면 안 된다. 여기에서도 숫자를 빼서 0으로 맞춘다. 이렇게 하지만 (r2+1, c2+1)부터는 누적합의 영향을 받지 않기 때문에 숫자를 빼줄 필요가 없다. 이번에는 거꾸로 숫자를 더해서 다시 0으로 만들어준다.

그런 다음 매 행마다 누적합을 수행하고, 매 열마다 누적합을 수행하면 된다.

def solution(board, skill):
    n, m = len(board), len(board[0])
    tmp = [[0]*(m+1) for _ in range(n+1)]
    
    for ty, r1, c1, r2, c2, degree in skill:
        if ty == 1: degree *= -1
        tmp[r1][c1] += degree
        tmp[r1][c2+1] -= degree
        tmp[r2+1][c1] -= degree
        tmp[r2+1][c2+1] += degree

    for i in range(n):
        for j in range(m):
            tmp[i][j+1] += tmp[i][j]
    
    for j in range(m):
        for i in range(n):
            tmp[i+1][j] += tmp[i][j]
         
    ans = 0
    for i in range(n):
        for j in range(m):
            board[i][j] += tmp[i][j]
            if board[i][j] > 0:
                ans += 1
                
    return ans