[Python] 2022 KAKAO BLIND RECRUITMENT : 파괴되지 않은 건물(누적합 사용)

2022 KAKAO BLIND RECRUITMENT : 파괴되지 않은 건물

문제풀이

이 문제는 간단하게 보일 수 있지만 3중 for문을 사용하여 풀면 시간 복잡도가 O(N*M)이 되어 효율성에서 실패한다.
누적합을 사용하여 이를 O(N)으로 줄여야합니다.

1. 누적합을 하기 위해 2차원 배열 tmp에 주어진 board의 가로, 세로 칸보다 1칸씩 늘려 선언해준다.

2. 적의 공격과 아군의 회복 값들을 tmp 값에 누적합 기록을 해준다.

3. 행 누적합을 해준다.

4. 열 누적합을 해준다.

5. 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]

2. 행누적합 →

   [N, N, N, 0],
   [0, 0, 0, 0],
   [0, 0, 0, 0],
   [-N, -N, -N, 0]

3. 열누적합 ↓

   [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