참고
문제해설
문제 로직고민
NOTE
•
효율성을 고려하지 않는다면, 가장 단순하게 이중 for문으로 해결할 수 있다.
◦
하지만 효율성을 체크하는 문제이기 때문에 그렇게 풀면 틀린다.
◦
실제 효율성을 고민해봤으나 결국 찾지못하고 공식 풀이를 보았는데, 정확성의 경우 50%이상이 정답을 맞춘반면, 효율성에서 1.86이라는 처참한 기록이 있었다.
◦
누적합을 이용한 방식으로 해결해야하는데, 이에대한 풀이는 공식 사이트를 참고하자.
n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n
JavaScript
복사
0,0 2,2의 범위를 누적합으로 표현하는 방법!
작성코드
NOTE
class Solution {
public int solution(int[][] board, int[][] skill) {
int row = board.length;
int column = board[0].length;
int[][] board2 = new int[row+1][column+1];
// skill -> type(1 공격, 2 회복), 범위, 계수)
for(int[] sk : skill){
int type = sk[0] == 1 ? -1 : 1;
int[] sp = {sk[1], sk[2]};
int[] dp = {sk[3], sk[4]};
int degree = sk[5] * type;
board2[sp[0]][sp[1]] += degree;
board2[dp[0] + 1][sp[1]] += degree * -1;
board2[sp[0]][dp[1] + 1] += degree * -1;
board2[dp[0] + 1][dp[1] + 1] += degree;
}
int answer = 0;
for(int y=0; y<row; y++){
for(int x=1; x<column; x++){
board2[y][x] += board2[y][x-1];
}
}
for(int x=0; x<column; x++){
for(int y=1; y<row; y++){
board2[y][x] += board2[y-1][x];
}
}
for(int y=0; y<row; y++){
for(int x=0; x<column; x++){
if(board[y][x] + board2[y][x] > 0) answer++;
board[y][x] += board2[y][x];
}
}
return answer;
}
}
Java
복사
다른사람 풀이
NOTE
class Solution {
static int[][] mapSum;
static int N, M;
public int solution(int[][] board, int[][] skill) {
int answer = 0;
N = board.length;
M = board[0].length;
mapSum = new int[N + 1][M + 1];
for (int[] a : skill) {
int r1 = a[1];
int c1 = a[2];
int r2 = a[3];
int c2 = a[4];
int attack = a[5] * (a[0] == 1 ? -1 : 1);
mapSum[r1][c1] += attack;
mapSum[r1][c2 + 1] += (attack * -1);
mapSum[r2 + 1][c1] += (attack * -1);
mapSum[r2 + 1][c2 + 1] += attack;
}
sum();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (board[i][j] + mapSum[i][j] > 0) answer++;
}
}
return answer;
}
public static void sum() {
// 좌우
for (int c = 1; c < M; c++) {
for (int r = 0; r < N; r++) {
mapSum[r][c] += mapSum[r][c - 1];
}
}
// 상하
for (int r = 1; r < N; r++) {
for (int c = 0; c < M; c++) {
mapSum[r][c] += mapSum[r - 1][c];
}
}
}
}
Java
복사
코드가 깔끔하다? 사실 풀이방법을 알면 쉬운문제라 참고할건 없는것같다.