[Programmers] 파괴되지 않은 건물(Python3)
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
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만큼 건물의 내구도를 높입니다.
- type은 1 혹은 2입니다.
- 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.
입출력 예
| 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 해야 합니다.
첫번째 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from itertools import product
def solution(board, skills):
alive = len(board) * len(board[0])
for skill in skills:
attack_type = skill[0]
start = [skill[1], skill[2]]
end = [skill[3], skill[4]]
amount = skill[5]
print(attack_type, start, end, amount)
print(get_coverage(start, end))
coverage = get_coverage(start, end)
for cover in coverage:
prev_target = board[cover[0]][cover[1]]
if attack_type == 1:
board[cover[0]][cover[1]] -= amount
target = board[cover[0]][cover[1]]
if prev_target > 0 and target <= 0:
alive -= 1
else:
board[cover[0]][cover[1]] += amount
target = board[cover[0]][cover[1]]
if prev_target <= 0 and target > 0:
alive += 1
print(alive)
def get_coverage(start, end):
start_x, start_y = start[0], start[1]
end_x, end_y = end[0], end[1]
x_list = []
y_list = []
for i in range(start_x, end_x + 1):
x_list.append(i)
for i in range(start_y, end_y + 1):
y_list.append(i)
return list(product(x_list, y_list))
1
2
3
cases = [[[[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]]], [[[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]]]]
for case in cases:
solution(case[0], case[1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 [0, 0] [3, 4] 4
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4)]
1 [2, 0] [2, 3] 2
[(2, 0), (2, 1), (2, 2), (2, 3)]
2 [1, 0] [3, 1] 2
[(1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
1 [0, 1] [3, 3] 1
[(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
10
1 [1, 1] [2, 2] 4
[(1, 1), (1, 2), (2, 1), (2, 2)]
1 [0, 0] [1, 1] 2
[(0, 0), (0, 1), (1, 0), (1, 1)]
2 [2, 0] [2, 0] 100
[(2, 0)]
6
효율성 문제가 있는 문제답게 역시 혼자 풀이한 풀이로는 정확성 테스트만을 통과할 수 있었습니다.
이 문제의 효율성 테스트까지 통과하도록 풀기 위해서는 배열의 ‘누적합’을 사용해야 합니다.
누적합을 사용하면 배열의 특정 부분만큼을 감소시키거나 증가시키는 것을 시간 복잡도 O(N*M)에서 O(1)으로 처리할 수 있습니다.
먼저, 1차원 배열로 누적합을 설명해보겠습니다.
1
[0,0,0,0,0,0]
만약, 0~2번째 배열까이 N만큼을 감소시키고 싶은 경우에는, 다음과 같은 새로운 배열을 만듭니다.
1
[-N, 0, 0, N, 0, 0]
여기서, N의 위치가 2번째가 아닌 3번째 인덱스에 위치한것을 주의하셔야합니다.
편의상 N을 2라고 가정해봅시다.
1
[-2, 0, 0, 2, 0, 0]
위 그림처럼 차례대로 왼쪽값을 오른쪽에 더합니다.
1
[-2, -2, -2, 0, 0, 0]
그럼 다음과 같이 0에서 2인덱스 까지 2씩 감소시킬 수 있습니다.
그럼 만약 반대로 0에서 2인덱스 까지 2씩 증가시키려면 어떻게 해야할까요?
1
[2, 0, 0, -2, 0, 0]
당연히 위처럼 반대로 해당 인덱스의 값을 변경해주면 됩니다.
그렇다면 이차원 배열의 경우는 어떻게 하면 될까요?
위 그림처럼 누적합 배열에 다음과 같이 범위의 시작과 끝은 -N, 나머지 범위는 N으로 마킹해주고 행방향으로 한번 누적합, 열 기준으로 한번 누적합을 진행해주면 됩니다.
정확성, 효율성 모두 통과하는 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def solution(board, skills):
answer = 0
record = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
for skill in skills:
attack_type = skill[0]
start = [skill[1], skill[2]]
end = [skill[3], skill[4]]
amount = skill[5]
if attack_type == 2:
amount = -amount
record[start[0]][start[1]] += -amount
record[end[0] + 1][end[1] + 1] += -amount
record[start[0]][end[1] + 1] += amount
record[end[0] + 1][start[1]] += amount
for i in range(len(record) - 1):
for j in range(len(record[0]) - 1):
record[i][j + 1] += record[i][j]
for j in range(len(record[0]) - 1):
for i in range(len(record) - 1):
record[i + 1][j] += record[i][j]
for i in range(len(board)):
for j in range(len(board[i])):
board[i][j] += record[i][j]
if board[i][j] > 0:
answer += 1
return answer
1
2
3
cases = [[[[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]]], [[[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]]]]
for case in cases:
print(solution(case[0], case[1]))
1
2
3
4
[[1, 0, 0, 0, 1], [3, 2, 0, 0, 1], [1, 0, -2, -2, 1], [3, 2, 0, 0, 1]]
10
[[-1, 0, 3], [2, -1, 2], [107, 4, 5]]
6
다음과 같이 record라는 누적합을 사용하기 위한 배열을 만들어 준뒤, 여기에 해당 범위에 더하고 빼줄 수를 마킹 해준뒤, 누적합을 실행하고 이를 원래 board와 함께 더해주면 해당 스킬들이 사용되고 난 후의 건물들의 모습을 O(N)의 시간으로 구할 수 있다.
댓글남기기