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

---

풀이

정답 해설을 보고 풀었다. 내가 이해한 바를 다시 기록하고, 이 문제를 풀이하는데 사용된 테크닉을 기억하기 위한 풀이이다.

1. 1차원 배열의 연속된 범위에 값을 누적하기

모든 값이 0으로 초기화된, 길이가 8인 배열 A가 있다.

다음과 같은 연산을 순차적으로 적용한다고 해보자

• 인덱스 2~6에 5를 더하기
• 인덱스 3~7에 2를 빼기
• 인덱스 0~5에 1을 더하기

아래와 같은 과정을 거치게 될 것이다.

그리고 이러한 과정을 그대로 코드로 구현한다면,
각 연산을 실행할 때 마다 각 연산이 적용되는 범위만큼을 순회할 것이고
대략 아래와 같은 코드일 것이다.

# operation: 연산이 담긴 배열. 각 연산은 적용될 범위의 시작, 끝 그리고 값으로 구성된다.
for op in operation:
	start, end, value = op
    for i in range(start, end+1):
    	A[i] += value

그러나 아래와 같은 방법을 이용하면 매 순회마다 연산을 직접 적용하지 않고도 마지막에 동일한 결과를 얻을 수 있다.

각 범위의 시작 인덱스에 연산을 적용할 값을 더해주고,
범위의 마지막 인덱스+1에 그 값의 부호를 반대로하여 더해준다.
마지막 인덱스+1 에 접근해야 하기 때문에 배열의 길이를 1 늘려주어야 한다.

이렇게 구해진 배열의 누적합을 계산하면, (배열의 왼쪽 -> 오른쪽)
구하고자 하는 배열을 확인할 수 있다.

그래서 위에서 구현한 코드를 아래와 같이 바꿀 수 있다.

# A의 길이는 9
for op in operation:
	start, end, value = op
    A[start] += value
    A[end+1] -= value
    
for i in range(1, len(A)):
	A[i] += A[i-1]

이 아이디어의 핵심은 범위의 끝+1 인덱스에 부호를 역전시킨 값을 더해주어
정해진 범위 안에서만 누적합이 계산되도록 한 것이다.

2. 2차원 배열에 적용하기

문제에서 주어진 board는 2차원 배열이며, skill이 적용되는 범위는 다음과 같은 식이다.

2차원 배열에서도 마찬가지로 위의 방법을 적용할 수 있다.

차이점은 2차원 배열이기 때문에 범위인 직사각형의 각 모서리에 해당하는 부분에
범위 바깥의 누적합을 상쇄시키기 위한 값을 더해주었다는 것이다.

여기서 가로, 세로 방향으로 누적합을 계산하면 같은 결과를 확인할 수 있다.

---

코드

def solution(board, skill):
    answer = 0
    skill_sum = [[0] * (len(board[0])+1) for _ in range(len(board)+1)]
    for i in range(len(skill)):
        do_skill(skill_sum, skill[i])

    for i in range(len(skill_sum)):
        for j in range(1, len(skill_sum[i])):
            skill_sum[i][j] += skill_sum[i][j-1]

    for j in range(len(skill_sum[i])):
        for i in range(1, len(skill_sum)):
            skill_sum[i][j] += skill_sum[i-1][j]

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

def do_skill(skill_sum, s):
    t, r1, c1, r2, c2, degree = s
    if t == 1:
        degree = -degree
    skill_sum[r1][c1] += degree
    skill_sum[r2+1][c2+1] += degree
    skill_sum[r1][c2+1] += -degree
    skill_sum[r2+1][c1] += -degree