카카오 코테 - 파괴되지 않는 건물(Python, Java)

풀이과정 

처음에는 무식하게 for 문을 이용해서 했지만 역시나 효율성 테스트에서 떨어졌다. 그리고 나서 솔직히 다른 풀이를 생각해 내지 못했다. 그래서 풀이를 찾아본 결과 "누적합" 을 이용하는 문제였다. 보통 일반적으로 누적합이라고 하면 1차원 누적합을 생각하기 쉽지만 2차원 누적합이어서 조금 생소하게 생각했었던 것 같다. 조금 이론적인 부분에 대해서도 찾아볼 필요가 있다는 생각이 들었다. 

 

가령 예를 들어 파란색 부분에 400 을 집어넣고 싶다면 

x 축에서 누적합을 더한 후에

y축에서 누적합을 구하면 깔끔하게 우리가 원하는 결과가 나온다.

이런식으로 for 문이 아닌 누적합을 이용해서 구할시 O(N * N) 이라는 시간복잡도로 구할 수 있다.

 

이를 이용해서 풀이를 구해주면 된다. 

 

 

 

코드(Java)

import java.util.*;

class Solution {
    private static final int DESTROY  = 1;
    private static final int REPAIR = 2;
    
    public int solution(int[][] board, int[][] skills) {
        int answer = 0;
        int[][] boardSum = new int[board.length + 1][board[0].length + 1];
        
        for (int[] skill: skills) {
            int type = skill[0], r1 = skill[1], c1 = skill[2], r2 = skill[3], c2 = skill[4], degree = skill[5];
            if (type == DESTROY) {
                degree *= -1;
            }
            boardSum[r1][c1] += degree;
            boardSum[r2 + 1][c1] -= degree;
            boardSum[r1][c2 + 1] -= degree;
            boardSum[r2 + 1][c2 + 1] += degree;
        }
        
        for (int r = 0; r < board.length; r ++) {
            for (int c = 1; c < board[0].length; c ++) {
                boardSum[r][c] += boardSum[r][c - 1];
            }
        }
        
        for (int r = 1; r < board.length; r ++) {
            for (int c = 0; c < board[0].length; c ++) {
                boardSum[r][c] += boardSum[r - 1][c];
            }
        }
        
        
        for (int r = 0; r < board.length; r ++) {
            for (int c = 0; c < board[0].length; c ++) {
                if (board[r][c] + boardSum[r][c] > 0) {
                    answer += 1;
                }
            }
        }
        
        return answer;
    }
}

코드(Python)

# 파괴되지 않은 건물 -> 누적합을 이용한 풀이
# 시간복잡도 : O()
import sys


def solution(board: list, skill: list) -> int:
    answer = 0
    vertical, horizontal = len(board), len(board[0])
    sum_array = [[0] * horizontal for _ in range(vertical)]
    for selection, r1, c1, r2, c2, degree in skill:
        calculated_degree = degree * (-1 if selection == 1 else 1)
        sum_array[r1][c1] += calculated_degree
        if r2 + 1 < vertical:
            sum_array[r2 + 1][c1] += calculated_degree * -1
        if c2 + 1 < horizontal:
            sum_array[r1][c2 + 1] += calculated_degree * -1
        if r2 + 1 < vertical and c2 + 1 < horizontal:
            sum_array[r2 + 1][c2 + 1] += calculated_degree
    for y in range(vertical):
        for x in range(horizontal):
            if x > 0:
                sum_array[y][x] += sum_array[y][x - 1]
    for y in range(vertical):
        for x in range(horizontal):
            if y > 0:
                sum_array[y][x] += sum_array[y - 1][x]
    for y in range(vertical):
        for x in range(horizontal):
            if board[y][x] + sum_array[y][x] > 0:
                answer += 1
    return answer
\

출처

프로그래머스