문제를 정리해보자.
N x M 크기의 행렬 모양의 게임 맵이 있다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있다.
1. 건물은 적의 공격을 받으면 내구도가 감소한다.
2. 건물은 내구도가 0이하가 되면 파괴된다.
3. 건물은 아군의 회복 스킬을 받으면 내구도가 증가한다.
4. 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 된다.
적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수는 몇 개인가?
아래는 프로그래머스에 나온 예이다.
풀이를 생각해보자.
방법 1) 매번 적의 공격 혹은 아군의 회복 스킬을 기본 게임 맵의 내구도에 적용시킨다.
이 방법은 효율성 테스트에서 통과할 수 없다.
skill의 행의 길이는 최대 250,000이다.
board의 행의 길이는 N, 열의 길이는 M이다.
skill의 행의 길이만큼 반복문을 돌고, 돌 때마다 board의 모든 원소를 확인해야 한다.
board만 시간 복잡도를 계산해도 O(NM)으로 1,000,000으로 결국 시간초과가 발생한다.
방법 2) 누적합 이용
먼저, 1차원 배열에서의 누적합을 생각해보자.
예1) 길이가 5인 배열에서 0~2번째를 N만큼 감소시키고 싶다.
(편의를 위해 길이가 6인 배열을 만들었다.)
주의할 점은 N은 index 2번이 아닌 3번에 할당한다는 점이다.
예2) 길이가 5인 배열에서 0~2번째를 N만큼 감소시키고, 1~3번째를 M만큼 감소시키고 싶다.
문제는 2차원 배열로 주어졌다. 이제 2차원 배열에서의 누적합을 생각해보자.
예) 크기가 5X5인 배열에서 (0, 0)~(2, 2)번째를 N만큼 감소시키고 싶다.
(편의를 위해 크기가 6x6인 배열을 만들었다.)
누적합 범위를 기록한 후, 마지막에 한 번만 누적합을 진행하기 때문에 시간 복잡도가 O(1)이다. ?????
구현해보자.
방법 1) 매번 적의 공격 혹은 아군의 회복 스킬을 기본 게임 맵의 내구도에 적용시킨다.
def solution(board, skill):
row = len(board)
col = len(board[0])
check = 0
for type, r1, c1, r2, c2, degree in skill:
# 피해
if type == 1:
degree = -degree
for i in range(r1, r2+1):
for j in range(c1, c2+1):
board[i][j] += degree
# 파괴되지 않은 건물
for i in range(0, row):
for j in range(0, col):
if board[i][j] > 0:
check += 1
return check
solution([[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]])
방법 2) 누적합 이용
def solution(board, skill):
answer = 0
row = len(board)
col = len(board[0])
tmp = [[0] * (col + 1) for _ in range(row + 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 i in range(len(tmp) - 1):
for j in range(len(tmp[0]) - 1):
tmp[i + 1][j] += tmp[i][j]
answer = 0
# 기존 배열과 합체
for i in range(row):
for j in range(col):
board[i][j] += tmp[i][j]
# 파괴되지 않은 건물
if board[i][j] > 0: answer += 1
return answer'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 다단계 칫솔 판매 (0) | 2022.02.21 |
|---|---|
| [프로그래머스][2021 Dev-Matching: 웹 백앤드 개발자(상반기)][Python] 로또의 최고 순위와 최저 순위 (0) | 2022.02.21 |
| [프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] k진수에서 소수 개수 구하기 (2) | 2022.02.10 |
| [프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 양과 늑대 (0) | 2022.02.07 |
| [프로그래머스][2022 KAKAO BLIND RECRUITMENT][Python] 주차 요금 계산 (0) | 2022.02.07 |
