이 문제는 간단하게 보일 수 있지만 3중 for문을 사용하여 풀면 시간 복잡도가 O(N*M)이 되어 효율성에서 실패한다.
누적합을 사용하여 이를 O(N)으로 줄여야합니다.
- 누적합을 하기 위해 2차원 배열 tmp에 주어진 board의 가로, 세로 칸보다 1칸씩 늘려 선언해준다.
- 적의 공격과 아군의 회복 값들을 tmp 값에 누적합 기록을 해준다.
- 행 누적합을 해준다.
- 열 누적합을 해준다.
- tmp에 기존의 board 값을 더해주며, 파괴된 건물들을 확인해준다.
※ 누적 합 이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다. 시작점은 항상 첫번째 원소이며, R번째 원소까지의 합을 앞에서부터 쭉 더해오는 패턴입니다.
ex) 배열의 0번째부터 4번째 값에 N을 더하고 싶은 경우, 시작 값을 N으로 하고, 4+1번째에 -N으로 설정한다. = [N, 0, 0, 0, -N][N, 0, 0, 0, -N] -> [N, N, 0, 0, -N] -> [N, N, N, 0, -N] -> [N, N, N, N, -N] -> [N, N, N, N, 0]
이렇게 하면 원하는 대로 0~4번째 값에 N을 더할 수 있다.
2차원 배열도 크게 어렵지 않다.
ex) (0,0)부터 (2,2)까지 범위에 N을 더하고 싶은 경우,
1. 초기[N, 0, 0, -N],
[0, 0, 0, 0],
[0, 0, 0, 0],
[-N, 0, 0, N]
행누적합 →
[N, N, N, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[-N, -N, -N, 0]열누적합 ↓
[N, N, N, 0],
[N, N, N, 0],
[N, N, N, 0],
[0, 0, 0, 0]위와 같이 2차월 배열도 누적합을 적용할 수 있다.
def solution(board, skill): answer = 0 tmp = [[0] * (len(board[0])+1) for _ in range(len(board)+1)] # 문제 풀이 1번 # 문제 풀이 2번 for type, r1, c1, r2, c2, degree in skill: if type == 1: degree = -degree tmp[r1][c1] += degree tmp[r2+1][c2+1] += degree tmp[r1][c2+1] += -degree tmp[r2+1][c1] += -degree # 문제 풀이 3번 for i in range(len(tmp)-1): for j in range(len(tmp[0])-1): tmp[i][j+1] += tmp[i][j] # 문제 풀이 4번 for i in range(len(tmp[0])-1): for j in range(len(tmp)-1): tmp[j+1][i] += tmp[j][i] # 문제 풀이 5번 for i in range(len(board)): for j in range(len(board[0])): board[i][j] += tmp[i][j] if board[i][j] > 0: answer += 1 return answer