2022.03.01 [프로그래머스] (python 파이썬) 파괴되지 않은 건물

 

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

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

• 파괴되지 않은 건물

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

 

 

---

풀이

아래의 코드는 잘 동작하지만 이벤트가 발생할 때마다 2차원배열을 모두 돌면서 업데이트하는 곳에서 O(N*M)의 시간이 걸린다. 그래서 효율성 테스트를 통과하지 못한다.

def solution(board, skill):
    answer = 0
    for i in skill:
        t,r1,c1,r2,c2,degree=i
        for x in range(r1,r2+1):
            for y in range(c1,c2+1):
                if t==1:
                    board[x][y]-=degree
                else:
                    board[x][y]+=degree
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j]>0:
                answer+=1
    return answer

 

아래의 누적합 설명은 아래의 링크에서 가져왔습니다.

https://kimjingo.tistory.com/155#comment17238176

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

효율성 테스트 통과 방법

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

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

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

1

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

cs

 

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

누적합 절차

1

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

cs

 

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

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

1

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

cs

 

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

1

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

cs

 

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

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

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

1 2 3 4 5 6

[[ -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]]

cs

 

위의 배열을 누적합하는 절차는 다음과 같습니다.

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

 

아래의 코드는 위에서 설명한 누적합을 적용하여 작성한 코드이다. 누적 합을 적용하니 효율성 테스트도 통과!!

def solution(board, skill):
    answer = 0
    # 누적합을 기록 할 배열 생성 ( board배열보다 1크게 생성)
    arr=[[0]*(len(board[0])+1) for i in range(len(board)+1)]
    # 각 상황에 맞게 누적합 기록
    for i in skill:
        t,r1,c1,r2,c2,degree=i
        if t==1:
            arr[r1][c1]-=degree
            arr[r1][c2+1]+=degree
            arr[r2+1][c1]+=degree
            arr[r2+1][c2+1]-=degree
        else:
            arr[r1][c1]+=degree
            arr[r1][c2+1]-=degree
            arr[r2+1][c1]-=degree
            arr[r2+1][c2+1]+=degree
            
    # 가로먼저 누적합 적용
    for i in range(len(board)):
        for j in range(len(board[0])):
            arr[i][j+1]+=arr[i][j]
            
    #세로 누적합 적용
    for i in range(len(board[0])):
        for j in range(len(board)):
            arr[j+1][i]+=arr[j][i]
            
    #기존 배열에 누적합을 더해줌
    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j]+=arr[i][j]
            #만약 누적합을 더한 board가 0보다 크면 
            #해당 건물은 파괴되지 않았기 때문에 answer증가
            if board[i][j]>0:
                answer+=1
    return answer