[Programmers] 파괴되지 않은 건물 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT

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

코딩테스트 연습 - 파괴되지 않은 건물

---

이 문제는 쉬워보이지만 효율성 테스트를 통과하기 어려운 문제입니다. 

효율성 테스트 실패 코드

문제를 처음 읽고 생각나는대로 알고리즘을 푼다면 보통 다음과 같이 코드를 작성했을 것입니다.

def solution(board, skill):
    answer = 0
 
    for type, r1, c1, r2, c2, degree in skill:
        # (r1, c1) ~ (r2, c2) 값 추가
        for y in range(r1, r2+1, 1):
            for x in range(c1, c2+1, 1):
                board[y][x] += degree if type == 2 else -degree # type == 2 인 경우 -degree 추가
 
    for row in board:
        answer += len(list(filter(lambda x: x > 0, row))) # x > 0 이상인 리스트의 길이를 answer에 추가함
 
    return answer

위 코드는 틀린 코드는 아니지만 6~8번 라인에서 2차원 배열의 원소를 일일이 참조하기 때문에 시간 복잡도가 O(N*M)이 되게 됩니다. 따라서 효율성 테스트에서는 통과를 할 수 없습니다.

효율성 테스트 실패

효율성 테스트 통과 방법

시간 복잡도가 O(N*M)이기 때문에 이를 O(N) 혹은 O(1)로 줄여야합니다. 

이때 '누적합'을 이용하면 시간 복잡도를 줄일 수 있습니다. 2차원 배열의 누적합을 이해하기 위해 우선 1차원 배열의 누적합을 예로 들어보겠습니다.

길이가 5인 배열에서 만약 0~2번째 까지 N만큼 감소시키고 싶은 경우에 다음과 같이 새로운 배열을 만듭니다. (코드상의 편의를 위해 길이가 6인 배열로 생성하였습니다.) N이 2번째가아닌 3번째 인덱스에 할당된 것을 주의하세요.

[-N, 0, 0, N, 0, 0]

위의 배열을 0번째부터 마지막 인덱스까지 누적합을 하게되면 다음과 같습니다.

누적합 절차

[-N, -N, -N, 0, 0, 0]

0~2번째 원소가 -N이 되어 기존의 배열과 위의 배열을 합하게 되면 0~2번째 원소를 N만큼 감소시킬 수 있습니다. 이것이 누적합을 이용한 방법입니다. 이 방법이 어떻게 시간복잡도를 줄일 수 있는지 한 가지 예시를 더 보겠습니다.

길이가 5인 배열에서 만약 0~2번째 까지 N만큼 감소시키고 1~3번째 까지 M만큼 감소시키는 경우에는 다음과 같이 배열을 만듭니다.

[-N, -M, 0, N, M, 0]

위의 배열을 0번째부터 마지막 인덱스까지 누적합을 하게되면 다음과 같습니다.

[-N, -M-N, -M-N, -M, 0, 0]

아까와 동일하게 위의 배열을 기존의 배열과 합하게 되면 원하는 결과를 얻을 수 있습니다.

1차원 배열의 원소를 계속 모두 참조하여 더하는 경우 O(N)의 시간복잡도를 가집니다. 하지만 위의 방식으로 구현하게되면 누적합을 기록하는 배열에 값을 저장한 후 마지막에 한번만 누적합을 계산하여 배열과 더하면되므로 O(1)의 시간복잡도를 가질 수 있게 됩니다.

문제에서는 1차원 배열이 아니라 2차원 배열입니다. 2차원 배열이라고 해도 크게 다를게 없습니다. 다만 누적합을 기록하는 방식이 조금 다릅니다. 예를들어 5x5배열에서 (0,0)~(2,2)까지 N만큼 감소시키는 경우 다음과 같이 배열을 생성합니다.
(여기서도 코드의 편의를 위해 6x6 배열로 생성합니다.)

[[ -N,  0,  0,  N,  0,  0],
 [  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0],
 [  N,  0,  0, -N,  0,  0],
 [  0,  0,  0,  0,  0,  0],
 [  0,  0,  0,  0,  0,  0]]

2차원 배열 또한 마찬가지로 누적합 범위를 기록한 후 마지막에 한 번만 누적합을 진행하기 때문에 O(1)의 시간복잡도를 가지게 됩니다.

효율성 테스트 통과 코드

따라서 위의 절차를 코드로 구현하면 다음과 같습니다.

def solution(board, skill):
    answer = 0
    tmp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)] # 누적합 기록을 위한 배열
 
    for type, r1, c1, r2, c2, degree in skill:
        # 누적합 기록, 부호에 주의할 것
        tmp[r1][c1] += degree if type == 2 else -degree
        tmp[r1][c2 + 1] += -degree if type == 2 else degree
        tmp[r2 + 1][c1] += -degree if type == 2 else degree
        tmp[r2 + 1][c2 + 1] += degree if type == 2 else -degree
 
    # 행 기준 누적합
    for i in range(len(tmp) - 1):
        for j in range(len(tmp[0]) - 1):
            tmp[i][j + 1] += tmp[i][j]
 
    # 열 기준 누적합
    for j in range(len(tmp[0]) - 1):
        for i in range(len(tmp) - 1):
            tmp[i + 1][j] += tmp[i][j]
 
    # 기존 배열과 합함
    for i in range(len(board)):
        for j in range(len(board[i])):
            board[i][j] += tmp[i][j]
            # board에 값이 1이상인 경우 answer++
            if board[i][j] > 0: answer += 1
 
    return answer
 

5~10번째 라인에서의 부호, 12~20번째 라인에서 for loop의 tmp배열의 범위만 주의하세요.

따라서 누적합을 이용하여 배열의 합을 구하면 효율성 테스트를 통과할 수 있습니다.

효율성 테스트 통과

---

감사합니다.