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

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

https://school.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함수를 완성해 주세요.

---

제한사항

• 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	skill	result
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]]	[[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]]	10
[[1,2,3],[4,5,6],[7,8,9]]	[[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]	6

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

<초기 맵 상태>

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

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

마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다.

총, 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return 해야 합니다.

---

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

문제 설명 및 요점

• 2차원 그래프와 스킬 리스트가 주어진다.
• 스킬은 그래프 값을 증가시킬수도, 감소시킬수도 있다.
• 스킬이 모두 사용된 최종 결과가 양수인 칸의 개수를 세어 반환한다.

풀이

#구간합 #스위핑

• 정확성 테스트는 그냥 시뮬레이션 구현을 하면 정답이다.
• 문제는 효율성 테스트인데, 시간이 매우 빡빡하다.
• 시간을 줄이기 위해서, 주어진 리스트를 압축해야 한다.
  • board를 압축하면, 마지막 결과를 구할 때 손실 없이 원상복구 할 수 없다.
  • 따라서 skill 을 압축할 방법을 생각해보자.
  • 어차피 skill은 범위에 대한 증감이기 때문에, skill을 모두 계산한 결과를 board에 적용하는 방식으로 시간 복잡도를 줄일 수 있다.
• skill을 압축해보자.
  • 모든 스킬 범위를 조사하려면 \( O(NM) \) 이지만, 누적합을 이용하면 시간을 줄일 수 있다.
  • 처음에는 스킬 범위의 각 행에 대해 시작점에 +degree, 마지막 + 1 점에 -degree를 모두 적은 후 한 번에 누적합을 돌렸다. -> 이것도 시간초과가 발생한다.
  • 결국 위 아이디어를 2차원으로 확장해야 한다.
• 2차원 누적합을 이용한다.
  • 스킬 범위는 항상 직사각형이다. 좌상단과 우하단에는 +degree, 우상단과 좌하단에는 -degree를 적는다.
  • 좌상단을 제외한 나머지 점은 1칸씩 미뤄 적어줘야 한다는 점을 잊지 말자.
  • 이렇게 모든 스킬에 대해 사각형의 각 꼭짓점을 적었다면, 각 축을 기준으로 누적합을 구하면 된다.
  • board와 skill의 각 칸에 대해 연산 후 1 이상이면 카운트한다.

코드

def solution(board, skill):
    N = len(board)
    M = len(board[0])
    compressed = [[0] * (M + 1) for _ in range(N + 1)] #row, col
    for tp, r1, c1, r2, c2, degree in skill:
        degree = degree if tp == 2 else -degree
        compressed[r1][c1] += degree
        compressed[r1][c2 + 1] -= degree
        compressed[r2 + 1][c1] -= degree
        compressed[r2 + 1][c2 + 1] += degree

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

    return answer