[프로그래머스 Lv3] 파이썬 - 파괴되지 않은 건물

프로그래머스 - 파괴되지 않은 건물

# 조건

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

• 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함수를 완성해 주세요.

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

# 접근 방법

• 주어진 문제를 정확성 테스트만 통과하기 위해서는 브루트 포스로 풀어주면 된다.
  • board의 크기가 100 x 100 이하이고
  • skill의 개수가 100개 이하이기 때문에

def solution(board, skill):
    answer = 0
    N, M = len(board), len(board[0])
    for t, si, sj, ni, nj, degree in skill:
        if t == 1:
            for i in range(si, ni+1):
                for j in range(sj, nj+1):
                    board[i][j] -= degree
        else:
            for i in range(si, ni+1):
                for j in range(sj, nj+1):
                    board[i][j] += degree

    for i in range(N):
        for j in range(M):
            if board[i][j] > 0:
                answer += 1

    return answer

• 다만 효율성 테스트도 있기 때문에 다른 풀이 방법이 필요하다.
• skill이 주어지면서 내구도를 감소시키고 회복시키는 일이 반복 발생하므로 누적합을 생각해주었다.
• 주어지는 좌표의 [시작 행, 시작열], [시작 행, 마지막 열+1] 부터 마지막 행까지 주어지는 degree 값을 반대로 입력해주면 된다.
  • 이를 위해서 N+1만큼의 행, M+1만큼의 열을 가진 prefix 배열을 생성해준다.
  • 0, 0에서 3, 4까지 4씩 감소 시킨다면
  • [[-4, 0, 0, 0, 0, 4], [-4, 0, 0, 0, 0, 4], [-4, 0, 0, 0, 0, 4], [-4, 0, 0, 0, 0, 4]] 배열이 생성되고 이를 한 행씩 누적합 시킨다면
  • [[-4, -4, -4, -4, -4, 0], [-4, -4, -4, -4, -4, 0], [-4, -4, -4, -4, -4, 0], [-4, -4, -4, -4, -4, 0]] 가 되어 각 좌표마다 더해주거나 빼주는 값이 계산된다.

prefix = [[0] * (M+1) for _ in range(N)]
for t, si, sj, ni, nj, degree in skill:
    val = degree if t == 2 else -degree
    for i in range(si, ni+1):
        prefix[i][sj] += val
        prefix[i][nj+1] -= val

for i in range(N):
    for j in range(1, M):
        prefix[i][j] += prefix[i][j-1]

• 위의 경우도 효율성 테스트는 통과하지 못하였다..
• skill의 길이가 250000가 되므로 최악의 경우 행의 최대 개수 1000 * 250000이 되어 시간 초과가 발생한다.
• 따라서, 행의 경우도 반복문을 통해 하나하나 기록해주는 것이 아닌 시작 행과 마지막 행 +1 에 기록해준 후
• prefix 합을 가로 뿐만 아니라 세로로도 구해주면 된다.

def solution(board, skill):
    answer = 0
    N, M = len(board), len(board[0])
    prefix = [[0] * (M+1) for _ in range(N+1)]
    for t, si, sj, ni, nj, degree in skill:
        val = degree if t == 2 else -degree
        prefix[si][sj] += val
        prefix[si][nj+1] -= val
        prefix[ni+1][sj] -= val
        prefix[ni+1][nj+1] += val

    for i in range(N):
        for j in range(M):
            prefix[i][j+1] += prefix[i][j]
    for j in range(M):
        for i in range(N):
            prefix[i+1][j] += prefix[i][j]

    for i in range(N):
        for j in range(M):
            if board[i][j] + prefix[i][j] > 0:
                answer += 1

    return answer