[프로그래머스]Lv.3 파괴되지 않은 건물 (Python)

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/92344

풀이

2차원 배열을 순회하는 단순 구현으로도 쉽게 정답을 만들어낼 수 있다.

 

단, skill이 최악의 경우 250,000개가 전달되므로 이런 경우 단순한 시간복잡도 계산으로 시간초과가 발생할 수 있다는 것을 알 수 있다
그렇기때문에 수학적 기믹이 필요하다.

 

누적합을 이용해보자.

공격 또는 회복의 시작점과 끝점을 +n, -n으로 기록하게 되면 해당 범위에 모든 원소는 누적합 계산을 통해서 n만큼 적용시킬 수 있다.
skill마다 공격과 회복 유형에 맞게끔 시작과 끝을 기록하고 나서 누적합을 기록한다면 1차원인 상태에서는 올바르게 적용시킬 수 있다.

 

그러나, 2차원 배열에서는 세로축도 존재하므로 고려를 해야 한다.
그렇다면 세로축 범위에 끝에는 위 연산과 반대로 넣어보자.

 

예를 들어서,

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

 

에서 skill에 맞게 지정하면 아래와 같다

0 0 0 0
1 0 -1 0
0 0 0 0
-1 0 1 0

 

 

이제 가로세로 누적합 원리를 보자.

 

0 0 0 0
1 1 0 0
0 0 0 0
-1 -1 0 0

0 0 0 0
1 1 0 0
1 1 0 0
0 0 0 0

 

시작점과 끝점의 좌표를 x1, y1, x2, y2 라고 하고 범위, 공격이 m일 때,

 

 

(x1, y1), (x2 + 1, y2 + 1) 좌표에 -m,
(x2 + 1, y1), (x1, y2 + 1) 좌표에 +m을 기록하고 누적합 계산을 하면 된다.

제출 코드

def solution(board, skill):
    n, m = len(board), len(board[0])
    psum = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # 공격 혹은 회복 시작점과 끝점 기록
    for t, r1, c1, r2, c2, degree in skill:
        value = -degree if t == 1 else degree
        psum[r1][c1] += value
        psum[r1][c2 + 1] -= value
        psum[r2 + 1][c1] -= value
        psum[r2 + 1][c2 + 1] += value
    answer = 0

    # 가로축 계산
    for i in range(n + 1):
        for j in range(1, m + 1):
            psum[i][j] += psum[i][j - 1]

    # 세로축 계산
    for j in range(m + 1):
        for i in range(1, n + 1):
            psum[i][j] += psum[i - 1][j]

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