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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 파괴되지 않은 건물

새로 알게된 것들

1. 효율성을 보는 문제는 항상 어렵다
2. 누적합을 이런식으로 응용할 수 있구나

누적합을 이용하면 O(N)의 시간복잡도를 O(1)로 할 수 있다는 것과 누적합을 1차원배열이 아닌 2차원배열에도 적용이 가능하다는 것을 명심하자 ^오^b

풀이

해설: 2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설
혼자 해결하지 못하고 공식 해설을 보면서 해결하였다. 빨리 보길 다행이다. 며칠이 걸려도 해결 못 했을 것 같다.

코드

def solution(board, skill):
    
    sum_board = [[0 for _ in range(len(board[0]) + 1)] for _ in range(len(board) + 1)]
    for type, r1, c1, r2, c2, degree in skill:
        sum_board[r1][c1] += 2 * (type - 1.5) * degree
        sum_board[r1][c2 + 1] += - 2 * (type - 1.5) * degree
        sum_board[r2 + 1][c1] += - 2 * (type - 1.5) * degree
        sum_board[r2 + 1][c2 + 1] += 2 * (type - 1.5) * degree
    
    for row in range(len(sum_board)):
        for col in range(1, len(sum_board[0])):
            sum_board[row][col] += sum_board[row][col - 1]
            
    for col in range(len(sum_board[0])):
        for row in range(1, len(sum_board)):
            sum_board[row][col] += sum_board[row - 1][col]

    answer = 0
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] + sum_board[i][j] > 0:
                answer += 1
    
    return answer

느낀점

어떻게 풀지 모르겠는 문제는 과감히 해설이나 풀이를 봐야겠다. 문제를 어느정도 풀어서 내가 풀수 있는 문제인지 아닌지 어느정도 분간이 가능해진 것 같다.