2022 KAKAO BLIND RECRUITMENT 에서 6번 문제로 나왔던 '파괴되지 않은 건물'입니다.
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
함수를 완성해 주세요.
board
의 행의 길이 (= N
) ≤ 1,000board
의 열의 길이 (= M
) ≤ 1,000board
의 원소 (각 건물의 내구도) ≤ 1,000skill
의 행의 길이 ≤ 250,000skill
의 열의 길이 = 6skill
의 각 행은 [type, r1, c1, r2, c2, degree]
형태를 가지고 있습니다.(r1, c1)
부터 (r2, c2)
까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.board
의 행의 길이board
의 열의 길이board
의 행의 길이 (= N
) ≤ 100board
의 열의 길이 (= M
) ≤ 100board
의 원소 (각 건물의 내구도) ≤ 100skill
의 행의 길이 ≤ 100board | 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 |
누적합 알고리즘을 알고리즘을 확장한 IMOS법을 사용하여 해결하였습니다.
기존에 모든 index에 가중치를 입력함으로써 생기는 반복을 IMOS법은 시작과 종료만을 기록함으로써 크게 줄일 수 있습니다. 입력마다 시작지점에 가중치를 더하고, 종료지점에 반대 부호의 가중치를 더합니다. 그 후, 배열의 누적합을 계산하면 각각 인덱스의 가중치를 구할 수 있게 됩니다.
각 입력 i (0 ≤ i < C) 당 시작지점 S와 종료지점 E가(0 ≤ S < E ≤ T) 주어졌다고 했을 때,
나이브한 방식으로는, 각각의 입력이 속한 각 지점의 가중치 더하는 방법을 들 수 있습니다. 이 방식은 시간복잡도가 O(CT)
입니다.
IMOS법의 경우 입력당 시작지점, 종료지점만 기록을 하기 때문에 시간복잡도가 입력의 개수 C와 누적합을 계산하는 시뮬레이션 T를 더한 값 즉, O(C+T)
입니다.
광고 삽입 / 2021 KAKAO BLIND RECRUITMENT (1차원 형태의 IMOS법 문제)
1차원의 경우 위의 방식을 그대로 적용하면 되지만, 2차원의 경우 행 기준 누적합과 열 기준 누적합을 모두 구해야하기 때문에 네 지점의 좌표에 기록을 해야합니다.
누적합 계산을 완료한 후 생성된 배열과 board
를 더해 몇 개의 건물이 파괴되지 않았는지 카운트하면 해결이 됩니다.
IMOS법에 자세한 설명(삼각형 등 특수 좌표계로의 확장 등)
def skillCheck(s_map, skill): for action in skill: r1 = action[1]; c1 = action[2]; r2 = action[3]; c2 = action[4] degree = action[5] if action[0] == 1: # attack s_map[r1][c1] -= degree s_map[r1][c2+1] += degree s_map[r2+1][c1] += degree s_map[r2+1][c2+1] -= degree else: # restore s_map[r1][c1] += degree s_map[r1][c2+1] -= degree s_map[r2+1][c1] -= degree s_map[r2+1][c2+1] += degree for r in range(n+1): # 행 기준 누적합 for c in range(1, m+1): s_map[r][c] += s_map[r][c-1] for c in range(m+1): # 열 기준 누적합 for r in range(1, n+1): s_map[r][c] += s_map[r-1][c] return def solution(board, skill): global n, m n = len(board); m = len(board[0]) s_map = [[0]*(m+1) for _ in range(n+1)] skillCheck(s_map, skill) answer = 0 for r in range(n): for c in range(m): if s_map[r][c] + board[r][c] > 0: answer += 1 return answer