(생략)
https://school.programmers.co.kr/learn/courses/30/lessons/92344
문제
- 입력으로 행렬 2차원 배열 board[N][M] ( 1 <= N, M <= 1000 ), ( 1 <= board[i][j] <= 1000 )과 공격, 치료 목록이 담긴 2차원 배열 skill[i][j] ( 1 <= i <= 250000 ), ( 1 <=j <= 250000 ) 이 입력으로 들어옴.
- skill은 [type, r1, c1, r2, c2. degree] 형태로 구성됨.
- type 은 1(적의 공격, 내구도 하락) 또는 2(회복 스킬, 내구도 상승). (r1, c1)부터 (r2, c2)까지 직사각형 모양 범위에 있는 건물의 내구도를 degree ( 1 <= degree <= 500 ) 만큼 상승시키거나 하락시킴.
- 건물은 최종적으로 내구도가 1 이상이 되면 파괴되지 않은 상태가 된다.
초기 코드
class Solution {
public int solution(int[][] board, int[][] skill) {
int answer = 0;
for (int i = 0; i < skill.length; i++) {
int[] temp = skill[i];
if (temp[0] == 1) {
for (int j = temp[1]; j <= temp[3]; j++) {
for (int k = temp[2]; k <= temp[4]; k++) {
board[j][k] -= temp[5];
}
}
}
if (temp[0] == 2) {
for (int j = temp[1]; j <= temp[3]; j++) {
for (int k = temp[2]; k <= temp[4]; k++) {
board[j][k] += temp[5];
}
}
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] > 0) {
answer++;
}
}
}
return answer;
}
}
일단 되는대로 만들었더니
정확도는 전부 맞았는데 효율성이 바닥을 찍어서 전부 틀렸다.
어떻게 하면 시간 초과가 안 날 수 있을까
여러 방법을 생각해봐야겠다.
수정한 코드
class Solution {
public int solution(int[][] board, int[][] skill) {
int num = 0;
boolean[][] result = new boolean[board.length][board[0].length];
for (int i = 0; i < skill.length; i++) {
int[] temp = skill[i];
if (temp[0] == 1) {
for (int j = temp[1]; j <= temp[3]; j++) {
for (int k = temp[2]; k <= temp[4]; k++) {
board[j][k] -= temp[5];
if (board[j][k] < 1 && !result[j][k]) {
result[j][k] = true;
num++;
}
}
}
}
if (temp[0] == 2) {
for (int j = temp[1]; j <= temp[3]; j++) {
for (int k = temp[2]; k <= temp[4]; k++) {
board[j][k] += temp[5];
if (board[j][k] >= 1 && result[j][k]) {
result[j][k] = false;
num--;
}
}
}
}
}
int answer = board.length * board[0].length - num;
return answer;
}
}boolean 배열을 추가해서 무너진 건물을 세는 변수로 계산하는 방법을 해봤는데
시간이 조금 줄었나 싶긴 하지만 효율성 테스트가 여전히 모두 시간 초과이다.
다른 방법을 사용해야 될 것 같다.
문제는 쉬운데 효율성을 위해 필요한 알고리즘이 있는 것 같다.
필요한 배열 부분 전체를 살피면 시간 초과가 나기 때문에 배열의 전체를 보지 않아도 원하는 부분을 계산할 방법이 필요하다.
skill 사용 시 직사각형의 범위가 생기게 되는데 이 때 두 꼭짓점 또는 네 꼭짓점을 이용하여 구하는 방법을 사용해야 될 것 같다.
꼭짓점을 이용하여 변할 구간을 정한 뒤 한 번에 계산하는 방법이 필요한 것 같다.
누적합을 이용하면 될 것 같은데 감이 잘 안 잡힌다.
누적합으로 일단 수정해본 코드
int num = 0;
int[][] board = {{5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}, {5, 5, 5, 5, 5}};
int[][] skill = {{1, 0, 0, 3, 4, 4}, {1, 2, 0, 2, 3, 2}, {2, 1, 0, 3, 1, 2}, {1, 0, 1, 3, 3, 1}};
int[][] result = new int[board.length][board[0].length];
for (int i = 0; i < skill.length; i++) {
int[] temp = skill[i];
if (temp[0] == 1) {
temp[5] = -temp[5];
}
System.out.println(temp[0] + " " + temp[5]);
result[temp[1]][temp[2]] += temp[5];
result[temp[1]][temp[4]] += temp[5];
result[temp[3]][temp[2]] += temp[5];
result[temp[3]][temp[4]] += temp[5];
System.out.println(Arrays.deepToString(result));
}
int[][] sum = new int[board.length][board[0].length];
for (int i = 0; i < board.length; i++) { //가로로
sum[i][0] = result[i][0];
for (int j = 1; j < board[0].length; j++) {
sum[i][j] = result[i][j] + sum[i][j - 1];
}
}
for (int i = 0; i < board[0].length; i++) { //세로로
for (int j = 1; j < board.length; j++) {
sum[j][i] += sum[j - 1][i];
}
}
int answer = 0;
for (int i = 0; i < board.length; i++) { //최종 계산
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] + sum[i][j] > 0) {
answer++;
}
}
}
아직 결과가 제대로 출력되지 않아서 일단 구조만 만들어보았다.
이런 방법으로 만들면 될 것 같은데 어떻게 수를 맞춰야 될지 모르겠다.
가로 세로로 나눠서 계산하는 이유는 구조를 어떻게 해야 될지 모르겠어서 찾아보니 다들 저렇게 했길래 따라해봤다.
최종 코드
class Solution {
public int solution(int[][] board, int[][] skill) {
int answer = 0;
int[][] result = new int[board.length+1][board[0].length+1];
for (int i = 0; i < skill.length; i++) {
int[] temp = skill[i];
if (temp[0] == 1) {
temp[5] = -temp[5];
}
result[temp[1]][temp[2]] += temp[5];
result[temp[1]][temp[4]+1] -= temp[5];
result[temp[3]+1][temp[2]] -= temp[5];
result[temp[3]+1][temp[4]+1] += temp[5];
}
int[][] sum = new int[board.length+1][board[0].length+1];
for (int i = 0; i <= board.length; i++) { //가로로
sum[i][0] = result[i][0];
for (int j = 1; j <= board[0].length; j++) {
sum[i][j] = result[i][j] + sum[i][j - 1];
}
}
for (int i = 0; i <= board[0].length; i++) { //세로로
for (int j = 1; j <= board.length; j++) {
sum[j][i] += sum[j - 1][i];
}
}
for (int i = 0; i < board.length; i++) { //최종 계산
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] + sum[i][j] > 0) {
answer++;
}
}
}
return answer;
}
}
누적합 구하는 부분을 잘 몰라 다른 블로그를 참조하여 완전히 내가 만든 코드라 할 순 없기 때문에 코드 분석을 해봤다.
가로와 세로 부분으로 나누어 계산하는 이유는 제일 처음 주어진 건물 배열이 2차원 배열이기 때문에 가로와 세로로 나누어서 계산을 하는 것 같다.
가로와 세로를 동시에 계산하는 코드도 있었는데 그 방법은 행과 열을 번갈아가며 계산하는 방식인 것 같았다.
일단 result (int형 2차원 배열)에 모든 skill을 입력했을 때 result 배열은
| -4 | -1 | 0 | 0 | 1 | 4 |
| 2 | 0 | -2 | 0 | 0 | 0 |
| -2 | 0 | 0 | 0 | 2 | 0 |
| 2 | 0 | 0 | 0 | -2 | 0 |
| 4 | 1 | 2 | 0 | -1 | -4 |
처럼 되는데
처음에 왜 두 부분은 반대로 넣어줘야 되는지 몰랐는데 가로 계산을 하고 보니 한 줄 씩 줄어든다는 것을 알게 되어서 진짜 놀랐다.
sum 2차원 배열에서 가로열을 계산한 후의 배열이다.
맨 오른쪽 열이 모두 0으로, 세로 열을 계산하지 않아도 되는 구역이 됐다.
| -4 | -5 | -5 | -5 | -4 | 0 |
| 2 | 2 | 0 | 0 | 0 | 0 |
| -2 | -2 | -2 | -2 | 0 | 0 |
| 2 | 2 | 2 | 2 | 0 | 0 |
| 2 | 3 | 5 | 5 | 4 | 0 |
sum 2차원 배열에서 세로열을 계산한 후의 배열이다.
세로 열에서는 맨 아래 끝 행이 모두 0으로 바뀌며 계산이 필요하지 않는 곳이 된다.
| -4 | -5 | -5 | -5 | 4 | 0 |
| -2 | -3 | -5 | -5 | -4 | 0 |
| -4 | -5 | -7 | -7 | -4 | 0 |
| -2 | -3 | -5 | -5 | -4 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
따라서 마지막 계산은 기존 행렬에서 마지막 행과 마지막 열을 제외한 부분만 계산하면 된다.
이 부분은 맨 처음 주어지는 건물의 배치도와 같은 크기이다.
최종적으로 건물의 처음 내구도인 board 배열과 마지막에 만들어진 sum 배열의 같은 칸끼리 합쳐 해당 칸의 수가 1 이상일 경우에만 건물의 내구도가 남아 파괴되지 않은 것으로 계산하면 된다.
누적합 연습을 많이 해봐야 될 것 같다.
예전에 풀었는데 기억이 잘 나지 않는 것 같다.
누적합을 구할 때 필요한 계산 방법이나 어떠한 방식으로 합쳐야 되는지를 생각해내는 것이 어려운 것 같다.
'프로그래머스 문제 풀이 > 프로그래머스 (JAVA)' 카테고리의 다른 글
| JAVA 프로그래머스 Lv.3 여행경로 (0) | 2024.12.01 |
|---|---|
| JAVA 프로그래머스 Lv.3 스티커 모으기(2) (0) | 2024.11.28 |
| JAVA 프로그래머스 Lv.3 표 편집 (1) | 2024.11.13 |
| JAVA 프로그래머스 Lv.3 최고의 집합 (1) | 2024.11.09 |
| JAVA 프로그래머스 Lv.3 섬 연결하기 (0) | 2024.11.03 |