구조물을 삭제
남아 있는 구조물들을 체크할 때 그냥 맵 전체를 탐색하며 구조물인 것을 체크
본인은 테스트케이스는 통과하는 코드를 만들었지만, 채점시 모두 틀리게 나오는 코드였다.
더보기
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[][] solution(int n, int[][] build_frame) {
int[][] grid = new int[n+1][n+1];
for(int a[] : grid) {
Arrays.fill(a, -1);//-1로 초기화
}
for (int i = 0; i < build_frame.length; i++) {
int x = build_frame[i][0];//[0] =x
int y = build_frame[i][1];//[1] =y
int a = build_frame[i][2];//[2] =>a 0:기둥 1:보
int b = build_frame[i][3];//[3] =>b 0:삭제 1:설치
if (b == 0) {//삭제하는 경우
if(a==0){//기둥
//기둥위의 것이 왼쪽에 연결되어있는경우에만 지울수있음.
if(grid[x][y+1] != -1 && grid[x-1][y+1] ==1){
grid[x][y] = -1;//-1은 삭제된값
// System.out.println("삭제 기둥" + x+","+y);
}
}else{//보
if((x>0&&grid[x-1][y]==1&&y>0&&grid[x][y-1]==0)||
x+1<n&&grid[x+1][y]!=-1&&y-1>0&&grid[x+1][y-1]==0){
grid[x][y] = -1;
// System.out.println("삭제 보" + x+","+y);
}
}
} else if (b == 1) {//설치하는 경우
if (a == 0) {//기둥
//왼쪽 아래 보 _ㅣ or 아래 기둥 !
if (y == 0 || (x>=1 && grid[x - 1][y] == 1)|| (y>=1 && grid[x][y - 1] == 0)) {
grid[x][y] = 0;
// System.out.println(x+","+y+"ㅣ");
} else {
continue;
}
} else if (a == 1) {//보
//왼쪽에 보 or 아래에 기둥
if ((x>=1 && grid[x - 1][y] != -1) || (y>=1 && grid[x][y - 1] == 0) || (x+1<=n&& y-1>0&& grid[x+1][y-1]==0 )) {
// System.out.println(x+","+y+"ㅡ");
grid[x][y] = 1;
} else {
continue;
}
}
}
}
Queue<Integer> x = new LinkedList<>();
Queue<Integer> y = new LinkedList<>();
Queue<Integer> val = new LinkedList<>();
for(int i=0; i<grid.length; i++){
for(int j=0; j<grid[0].length; j++){
if(grid[i][j] != -1){
x.add(i);
y.add(j);
val.add(grid[i][j]);
}
}
}
int[][] answer = new int[x.size()][3];
int size=x.size();
for(int i=0; i<size; i++){
answer[i][0]= x.poll();
answer[i][1]= y.poll();
answer[i][2]= val.poll();
// System.out.println(answer[i][0] + "," +answer[i][1] + ": " + answer[i][2]);
}
return answer;
}
}흑흑ㅜㅜ
- 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
- 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
위 조건들을 이용하여 아래의 문제를 해결한다.
위와 같은 삭제를 할때의 문제 해결에 어려움이 있었다.
<삭제는 아래와 같이 작동한다>
우선 삭제할 위치의 구조물을 삭제한다.
그 후, 남아 있는 모든 구조물들을 체크하여 위의 두 규칙을 여전히 만족하는지를 판단한다.
삭제한 구조물은 원상복구 시키고, 하나라도 위의 규칙을 만족하지 못한다면 false를, 모든 구조물들이 만족한다면 true를 리턴한다.
true를 리턴 받았으면 해당 위치의 구조물을 삭제한다.
남아 있는 구조물들을 체크할 때 그냥 맵 전체를 탐색하며 구조물인 것을 체크
class Solution {
private int n;
private boolean[][] cols, rows; // 기둥, 보
private final int COLUMN = 0, ROW = 1, REMOVE = 0, ADD = 1;
public int[][] solution(int n, int[][] build_frame) {
this.n = n;
int count = 0;
cols = new boolean[n + 3][n + 3];
rows = new boolean[n + 3][n + 3];
for (int[] frame : build_frame) {
int x = frame[0] + 1;
int y = frame[1] + 1;
if (frame[2] == COLUMN) { // 기둥
if (frame[3] == ADD && isExistCol(x, y)) { // 해당 위치에 기둥을 세울 수 있으면
cols[x][y] = true;
count++;
}
if (frame[3] == REMOVE && canRemove(x, y, COLUMN)) { // 삭제할 수 있으면
cols[x][y] = false;
count--;
}
} else { // 보
if (frame[3] == ADD && isExistRow(x, y)) {
rows[x][y] = true;
count++;
}
if (frame[3] == REMOVE && canRemove(x, y, ROW)) {
rows[x][y] = false;
count--;
}
}
}
int[][] answer = new int[count][3];
int index = 0;
for (int i = 1; i <= n + 1; i++) { // 남아 있는 기둥과 보 배열에 저장
for (int j = 1; j <= n + 1; j++) {
if (cols[i][j]) answer[index++] = new int[]{i - 1, j - 1, COLUMN};
if (rows[i][j]) answer[index++] = new int[]{i - 1, j - 1, ROW};
}
}
return answer;
}
private boolean isExistCol(int x, int y) { // x, y 위치에 존재할 수 있는지
return y == 1 || cols[x][y - 1] || rows[x][y] || rows[x - 1][y];
}
private boolean isExistRow(int x, int y) {
return cols[x][y - 1] || cols[x + 1][y - 1] || (rows[x - 1][y] && rows[x + 1][y]);
}
private boolean canRemove(int x, int y, int type) {
boolean result = true;
if (type == COLUMN) cols[x][y] = false; // 임시로 삭제
else rows[x][y] = false;
loop:
for (int i = 1; i <= n + 1; i++) {
for (int j = 1; j <= n + 1; j++) {
if (cols[i][j] && !isExistCol(i, j)) {
result = false;
break loop;
}
if (rows[i][j] && !isExistRow(i, j)) {
result = false;
break loop;
}
}
}
if (type == COLUMN) cols[x][y] = true; // 삭제했던 구조물 원상복구
else rows[x][y] = true;
return result;
}
}
제1출처 : leveloper.tistory.com/100
[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 기둥과 보 설치 (Java)
문제 : https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[..
leveloper.tistory.com
반응형
'코딩테스트 > Java' 카테고리의 다른 글
| (2021카카오) 순위검색 Java (0) | 2021.02.11 |
|---|---|
| (2021카카오) 메뉴 리뉴얼 Java (2) | 2021.02.09 |
| (2018카카오) 자물쇠와 열쇠 Java (0) | 2021.01.28 |
| [Java] 자바 진수변환 알고리즘 (0) | 2021.01.25 |
| (2018카카오) n진수 게임 Java (0) | 2021.01.25 |