[Python] 프로그래머스 / 2022 KAKAO BLIND RECRUITMENT / 파괴되지 않은 건물

문제 링크

누적합 기법

뭐 아래와 같이 행렬 일부에 같은 값을 더하거나 빼서 업데이트해야 할 일이 있다고 해보자.

 

직관적이긴 하지만 이러면 좀 비효율적이다. 이럴 때는

이러는 편이 조금 더 낫다. 왼쪽부터 누적합을 하면 같은 결과가 나오게 되기 때문이다.

이를 누적합 기법이라고 한다.

 

누적합 기법을 사용하지 않은 코드

는 굉장히 간단하다. 그냥 빡구현도 아니고 그냥 단순 구현 문제일 뿐이다.

def solution(board, skill):
    
    for heal_or_deal, r1, c1, r2, c2, degree in skill :
        #1 to -1; 2 to 1
        heal_or_deal = 2 * heal_or_deal - 3 
        for r in range(r1, r2+1) :
            for c in range(c1, c2+1) :
                board[r][c] += degree * heal_or_deal
    
    answer = 0
    for row in board :
        for elementary in row :
            if elementary > 0 :
                answer += 1
    
    return answer

 

이러면 정확성 문제는 다 맞힐 수 있는데, 효율성 문제를 하나도 풀 수 없게 된다. 애초에 2차원 행렬이 list니까, 시간효율성이 좋지 못하다.

 

아 그리고 "heal_or_deal = 2 * heal_or_deal - 3" 부분은, 힐이면 2, 딜이면 1로 인풋이 들어오는데, if문 써서 힐이면 더하고 딜이면 빼고 하기 귀찮으니까 

2->1, 1->-1로 변형해서 곱한 것이다.

 

정답코드

하여튼, 위와 같이 시간복잡도가 초과될 때, 누적합을 쓰면 된다.

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

        heal_deal_log[r1][c1] += degree
        heal_deal_log[r1][c2+1] -= degree
        heal_deal_log[r2+1][c1] -= degree
        heal_deal_log[r2+1][c2+1] += degree
    
    for i in range(n):
        for j in range(1, m):
            heal_deal_log[i][j] += heal_deal_log[i][j-1]
    
    for j in range(m):
        for i in range(1, n):
            heal_deal_log[i][j] += heal_deal_log[i-1][j]
    
    answer = 0
    for i in range(n):
        for j in range(m):
            board[i][j] += heal_deal_log[i][j]
            if board[i][j] > 0:
                answer += 1
    
    return answer