문제
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
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의 열의 길이 = 6skill의 각 행은[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만큼 건물의 내구도를 높입니다.
- 0 ≤ r1 ≤ r2 <
- type은 1 혹은 2입니다.
- 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.
정확성 테스트 케이스 제한 사항
- 1 ≤
board의 행의 길이 (=N) ≤ 100 - 1 ≤
board의 열의 길이 (=M) ≤ 100 - 1 ≤
board의 원소 (각 건물의 내구도) ≤ 100 - 1 ≤
skill의 행의 길이 ≤ 100- 1 ≤ degree ≤ 100
풀이
일단 완탐 접근을 해보자
class Solution {
public int solution(int[][] board, int[][] skill) {
for (int[] cast : skill) {
int type = cast[0];
int r1 = cast[1];
int c1 = cast[2];
int r2 = cast[3];
int c2 = cast[4];
int degree = cast[5];
if (type == 1) {
degree *= -1;
}
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
board[i][j] += degree;
}
}
}
int answer = 0;
for (int[] row : board) {
for (int col : row) {
if (col > 0) {
answer++;
}
}
}
return answer;
}
}로직 자체는 어려울 게 없다.
하지만 현재 위 코드의 시간 복잡도는 O(snm)으로 효율성 측면에서 위의 코드는 통과하기가 쉽지 않을 거 같다.
Prefix Sum풀이 방법 중 imos 라고도 불리는 알고리즘을 사용한다.
class Solution {
public int solution(int[][] board, int[][] skill) {
int n = board.length;
int m = board[0].length;
// 변화를 기록하기 위한 배열
int[][] map = new int[n + 2][m + 2];
for (int[] sk : skill) {
int type = sk[0], r1 = sk[1], c1 = sk[2], r2 = sk[3], c2 = sk[4], degree = sk[5];
if (type == 1) {
degree *= -1;
}
map[r1 + 1][c1 + 1] += degree; // 왼쪽 상단에 더해줌
map[r1 + 1][c2 + 2] -= degree; // 오른쪽 상단 경계 뒤에 빼줌
map[r2 + 2][c1 + 1] -= degree; // 왼쪽 하단 경계 아래에 빼줌
map[r2 + 2][c2 + 2] += degree; // 오른쪽 하단 경계 뒤에 더해줌
}
// 변화를 누적합으로 계산
for (int i = 1; i <= n + 1; i++) {
for (int j = 1; j <= m + 1; j++) {
map[i][j] += map[i - 1][j] + map[i][j - 1] - map[i - 1][j - 1];
}
}
int answer = 0;
// 변화를 기록한 배열을 기반으로 board에 변화를 적용
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
board[i - 1][j - 1] += map[i][j];
// 변화가 적용된 board의 값이 양수라면 answer 증가
if (board[i - 1][j - 1] > 0) {
answer++;
}
}
}
return answer;
}
}주석을 통하여 변화를 저장하는 배열의 작동 원리를 적어두었다.
(r1, c1) ~ (r2, c2) 의 범위가 대상이다.
- (0,0) ~ (r1, c1) 의 범위에는 degree를 더해준다.
- (0,0) ~ (r1, c2) 의 범위에는 degree를 빼준다.
- (0,0) ~ (r2, c1) 의 범위에는 degree를 빼준다.
- (0,0) ~ (r2, c2) 의 범위에는 degree를 더해준다.
이를 통해 변화가 일어나는 범위를 표시할 수 있다.
skill 배열 탐색이 끝난 후, map 배열을 누적합으로 계산하면 변화가 일어난 범위에 대한 누적합을 구할 수 있다.
이를 통해 board 배열에 변화를 적용할 수 있다.
시간 복잡도는 O(s+nm)이다.
결론
연속된 구간의 합을 구하는 문제는 Prefix Sum을 사용하면 효율적으로 풀 수 있다.
