🗒️알고리즘 분류
#구현, #시뮬레이션
📌기억해야 할 포인트
- 기둥과 보에 대한 설치 기록을 2개의 2차원 배열로 따로 나눠서 기록한다.
- 삭제 과정 처리를 잘해줘야 한다.
- 해당 위치의 기둥과 보를 먼저 삭제해준다.
- 해당 위치를 포함한 총 6격자의 기둥과 보들이 정상적인지 체크한다.(이미지의 파란점 1개와 빨간점 5개)
- 이때 해당 위치에 건축물이 있다면, 있는 건축물의 종류(기둥, 보)에 따라서 건축물이 존재할 수 있는지 체크해준다.
- 설치 과정에서 사용했던 canExistXxx 함수를 재사용하면 간단하게 구현할 수 있다.
- 정상이라면 그대로 반복문을 진행한다.
- 정상적이지 않다면 즉, 삭제하지 못한다면 삭제했던 기둥 혹은 보를 복원시킨다.
- 이때 해당 위치에 건축물이 있다면, 있는 건축물의 종류(기둥, 보)에 따라서 건축물이 존재할 수 있는지 체크해준다.
📝풀이 코드 (JAVA)
import java.util.*;
class Solution {
private static int[][] Columns;
private static int[][] Rows;
private static int N = 0;
public int[][] solution(int n, int[][] build_frame) {
Columns = new int[n+1][n+1];
Rows = new int[n+1][n+1];
N = n;
for (int[] frame : build_frame) {
int x = frame[0];
int y = frame[1];
int a = frame[2];
int b = frame[3];
if (a == 0) {
if (b == 1 && canExistColumn(x,y)) {
Columns[x][y] = 1;
} else {
Columns[x][y] = 0;
if (canDestroy(x,y) == false) {
Columns[x][y] = 1;
}
}
} else {
if (b == 1 && canExistRow(x,y)) {
Rows[x][y] = 1;
} else {
Rows[x][y] = 0;
if (canDestroy(x,y) == false) {
Rows[x][y] = 1;
}
}
}
}
List<int[]> answer = new ArrayList<>();
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= N; ++j) {
if (Columns[i][j] == 1) {
answer.add(new int[]{i,j,0});
}
if (Rows[i][j] == 1) {
answer.add(new int[]{i,j,1});
}
}
}
return answer.toArray(new int[0][]);
}
private boolean canExistColumn(int x, int y) {
if (y == 0) {
return true;
} else if (inRange(x,y-1) && Columns[x][y-1] == 1) {
return true;
} else if ((inRange(x-1,y) && Rows[x-1][y] == 1) || Rows[x][y] == 1) {
return true;
} else {
return false;
}
}
private boolean canExistRow(int x, int y) {
if ((inRange(x,y-1) && Columns[x][y-1] == 1) || (inRange(x+1,y-1) && Columns[x+1][y-1] == 1)) {
return true;
} else if ((inRange(x-1,y) && Rows[x-1][y] == 1) && (inRange(x+1,y) && Rows[x+1][y] == 1)) {
return true;
} else {
return false;
}
}
private boolean canDestroy(int x, int y) {
for (int i = x-1; i <= x+1; ++i) {
for (int j = y; j <= y+1; ++j) {
if (inRange(i,j)) {
if (Columns[i][j] == 1 && canExistColumn(i,j) == false) {
return false;
}
if (Rows[i][j] == 1 && canExistRow(i,j) == false) {
return false;
}
}
}
}
return true;
}
private boolean inRange(int x, int y) {
return 0 <= x && x <= N && 0 <= y && y <= N;
}
}🛠️Refactoring
다 풀고 다른 분들의 코드도 살펴봤는데, 풀이과정은 대체로 비슷했지만 아무래도 변수 명에서 아쉬움이 남아있었다.
- 기둥과 보를 나타내는 변수명이 적절한 것이 떠오르지 않아서 각각 Column, Row 로 지었는데 아무래도 Pillar, Bar 가 더 나은 것 같다.
- 문제 설명에서 나온 건축물의 종류를 나타내는 변수명 a → isPillarOrNot
- 문제 설명에서 나온 설치 혹은 삭제를 나타내는 변수명 b → isInstallingOrNot
📝리팩토링 이후의 코드
-
풀이 코드(JAVA)
import java.util.*; class Solution { private static int[][] Pillars; private static int[][] Bars; private static int N = 0; public int[][] solution(int n, int[][] build_frame) { Pillars = new int[n+1][n+1]; Bars = new int[n+1][n+1]; N = n; for (int[] frame : build_frame) { int x = frame[0]; int y = frame[1]; boolean isPillarOrNot = frame[2] == 0; boolean isInstallingOrNot = frame[3] == 1; if (isPillarOrNot) { if (isInstallingOrNot && canExistPillar(x,y)) { Pillars[x][y] = 1; } else { Pillars[x][y] = 0; if (canDestroy(x,y) == false) { Pillars[x][y] = 1; } } } else { if (isInstallingOrNot && canExistBar(x,y)) { Bars[x][y] = 1; } else { Bars[x][y] = 0; if (canDestroy(x,y) == false) { Bars[x][y] = 1; } } } } List<int[]> answer = new ArrayList<>(); for (int i = 0; i <= N; ++i) { for (int j = 0; j <= N; ++j) { if (Pillars[i][j] == 1) { answer.add(new int[]{i,j,0}); } if (Bars[i][j] == 1) { answer.add(new int[]{i,j,1}); } } } return answer.toArray(new int[0][]); } private boolean canExistPillar(int x, int y) { if (y == 0) { return true; } else if (inRange(x,y-1) && Pillars[x][y-1] == 1) { return true; } else if ((inRange(x-1,y) && Bars[x-1][y] == 1) || Bars[x][y] == 1) { return true; } else { return false; } } private boolean canExistBar(int x, int y) { if ((inRange(x,y-1) && Pillars[x][y-1] == 1) || (inRange(x+1,y-1) && Pillars[x+1][y-1] == 1)) { return true; } else if ((inRange(x-1,y) && Bars[x-1][y] == 1) && (inRange(x+1,y) && Bars[x+1][y] == 1)) { return true; } else { return false; } } private boolean canDestroy(int x, int y) { for (int i = x-1; i <= x+1; ++i) { for (int j = y; j <= y+1; ++j) { if (inRange(i,j)) { if (Pillars[i][j] == 1 && canExistPillar(i,j) == false) { return false; } if (Bars[i][j] == 1 && canExistBar(i,j) == false) { return false; } } } } return true; } private boolean inRange(int x, int y) { return 0 <= x && x <= N && 0 <= y && y <= N; } }⏰총 풀이시간
현명하고 성실하게 살자