[Java] 기둥과 보 설치
조건문 분기가 굉장히 까다로운 문제
처음에 딱맞는 크기의 배열을 만들었다가 복잡한 분기에 범위처리까지 하려니 너무 복잡해져서 배열의 크기를 늘렸다.
풀이 설명
작업을 순서대로 돌면서 기둥일 때와 보일 때를 분기하고 설치일 때와 삭제일 때를 분기한다.
기둥을 설치할 수 있는 조건
1. 바닥일 때
2. 기둥 위일 때
3. 보 위일 때
기둥을 삭제할 수 없는 조건
1. 위에 기둥이 있으면서 기둥을 지지해줄 보가 없을 때
2. 기둥 위에 보의 한쪽 끝이 있으면서 보를 지지해 줄 다른 기둥이나 양옆 보가 없을 때
보를 설치할 수 있는 조건
1. 한쪽 끝이 기둥일 때
2. 양옆에 보가 있을 때
보를 삭제할 수 없는 조건
1. 보 위에 기둥이 있으면서 기둥을 받쳐줄 기둥이 없고 보도 없을 때
2. 양옆에 보가 있으면서 보를 받쳐줄 기둥이 없을 때
작업을 전부 수행하고 난 후 남아있는 구조물들을 저장하고 기준에 맞춰 정렬한 후 반환해주면 된다.
코드
import java.util.PriorityQueue;
class Solution {
static class Structure implements Comparable<Structure> {
int y;
int x;
int what;
public Structure(int y, int x, int what) {
super();
this.y = y;
this.x = x;
this.what = what;
}
@Override
public int compareTo(Solution.Structure o) {
if (this.y == o.y && this.x == o.x)
return this.what - o.what;
if (this.x == o.x)
return this.y - o.y;
return this.x - o.x;
}
}
public int[][] solution(int n, int[][] build_frame) {
int[][] answer = {};
boolean[][][] board = new boolean[n + 2][n + 5][2];// [0]기둥, [1]보
for (int i = 0; i < build_frame.length; ++i) {
int x = build_frame[i][0] + 2;
int y = build_frame[i][1] + 1;
// 기둥
if (build_frame[i][2] == 0) {
// 설치
if (build_frame[i][3] == 1) {
// 바닥 위거나 기둥 위거나 보 위면
if (y == 1 || board[y - 1][x][0] || board[y][x][1] || board[y][x - 1][1]) {
// 기둥 설치
board[y][x][0] = true;
}
}
// 삭제
else {
// 위에 기둥이 있고 기둥 지지해줄 보가 없거나
if (board[y + 1][x][0] && (!board[y + 1][x - 1][1] && !board[y + 1][x][1]))
continue;
// 보의 한쪽끝이 있고 보의 반대편에 고정이 안돼있으면 삭제못함
if (board[y + 1][x - 1][1]
&& (!board[y][x - 1][0] && !(board[y + 1][x - 2][1] && board[y + 1][x][1])))
continue;
if (board[y + 1][x][1]
&& (!board[y][x + 1][0] && !(board[y + 1][x - 1][1] && board[y + 1][x + 1][1])))
continue;
board[y][x][0] = false;
}
}
// 보
else {
// 설치
if (build_frame[i][3] == 1) {
// 한쪽 끝이 기둥위거나 양쪽끝이 다른보면
if ((board[y - 1][x][0] || board[y - 1][x + 1][0]) || (board[y][x - 1][1] && board[y][x + 1][1]))
board[y][x][1] = true;
}
// 삭제
else {
// 한쪽끝에 기둥이 있고 아래쪽에 기둥이 없고 반대쪽에도 보가 없으면
if (board[y][x][0] && (!board[y - 1][x][0] && !board[y][x - 1][1]))
continue;
if (board[y][x + 1][0] && (!board[y - 1][x + 1][0] && !board[y][x + 1][1]))
continue;
// 양쪽끝에 보가 있고 보의 기둥이 없으면 삭제못함
if (board[y][x - 1][1] && (!board[y - 1][x - 1][0] && !board[y - 1][x][0]))
continue;
if (board[y][x + 1][1] && (!board[y - 1][x + 1][0] && !board[y - 1][x + 2][0]))
continue;
board[y][x][1] = false;
}
}
}
// 우선순위 큐에 전부 넣고 힙정렬
PriorityQueue<Structure> pq = new PriorityQueue<Solution.Structure>();
for (int i = 0; i < n + 2; ++i)
for (int j = 0; j < n + 5; ++j) {
if (board[i][j][0])
pq.add(new Structure(i - 1, j - 2, 0));
if (board[i][j][1])
pq.add(new Structure(i - 1, j - 2, 1));
}
answer = new int[pq.size()][3];
int idx = 0;
while (!pq.isEmpty()) {
Structure str = pq.poll();
answer[idx][0] = str.x;
answer[idx][1] = str.y;
answer[idx][2] = str.what;
++idx;
}
return answer;
}
}
Author And Source
이 문제에 관하여([Java] 기둥과 보 설치), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@codehh/Java-기둥과-보-설치저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)