[Java] 기둥과 보 설치

https://programmers.co.kr/learn/courses/30/lessons/60061

조건문 분기가 굉장히 까다로운 문제

처음에 딱맞는 크기의 배열을 만들었다가 복잡한 분기에 범위처리까지 하려니 너무 복잡해져서 배열의 크기를 늘렸다.

풀이 설명

작업을 순서대로 돌면서 기둥일 때와 보일 때를 분기하고 설치일 때와 삭제일 때를 분기한다.

기둥을 설치할 수 있는 조건
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;
    }
}

좋은 웹페이지 즐겨찾기