Algorithm/Programmers

[Lv.3] 기둥과 보 설치 - 자바

시롱시롱 2023. 7. 7. 00:19
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[][] solution(int n, int[][] build_frame) {
        int[][] answer = {};
        boolean[][] bar=new boolean[n+5][n+5];
        boolean[][] plate=new boolean[n+5][n+5];
        for (int[] ints : build_frame) {
            int x=ints[0];
            int y=ints[1];
            int isBar=ints[2];    //0:기둥 1:보
            int isDelete=ints[3];   //0:delete , 1:build
            if(isDelete==0){
                //delete
                if(isBar==0){
                    //기둥
                    //x,y+1에 기둥이 있다면 x,y or x-1,y에 보가 있어야 삭제를 할 수 있음
                    if(bar[x][y+1]){
                        //해당 지점에 보가 존재하지 않는다 -> 위의 기둥을 유지할 수 없다.
                        if(!((x>0&&plate[x-1][y+1])||plate[x][y+1]))
                            continue;
                    }
                    //삭제할 기둥 위에 보가 있는 경우(오른쪽)
                    if(plate[x][y+1]){
                        //보의 오른쪽 끝에 기둥이 없고 양 옆에 다른 보가 없다면 해당 기둥을 삭제할 수 없다.
                        if(!(bar[x+1][y]||((x>0&&plate[x-1][y+1])&&plate[x+1][y+1])))
                            continue;
                    }
                    //기둥 위에 보가 있다 (왼쪽)
                    if(x>0&&plate[x-1][y+1]){
                        //왼쪽 플레이트
                        if(!(bar[x-1][y]||((x>1&&plate[x-2][y+1])&&plate[x][y+1])))
                            continue;
                    }
                    bar[x][y]=false;

                }else{
                    //보

                    //보의 위치에 기둥이 존재한다.
                    if(bar[x][y]){
                        //그 아래에 다른 기둥이 없고 삭제할 보의 왼쪽의 보가 존재하지 않다면
                        //해당 위치의 기둥이 존재할 수 없기에 삭제를 하지 못한다.
                        if(!(bar[x][y-1]||(x>0&&plate[x-1][y])))
                            continue;
                    }
                    //보의 오른쪽 끝에 기둥이 존재한다.
                    if(bar[x+1][y]){
                        //그 아래에 다른 기둥이 없고 삭제할 보의 오른쪽에 보가 존재하지 않다면
                        //해당 위치의 기둥이 존재할 수 없기에 삭제하지 못한다.
                        if(!(bar[x+1][y-1]||plate[x+1][y]))
                            continue;
                    }
                    //양 옆의 plate가 기둥과 모두 연결되어 있어야 함

                    //오른쪽 보가 존재하는 경우
                    if(plate[x+1][y]){
                        //오른쪽 보의 양 끝에 기둥이 존재하지 않는다면 x,y보를 삭제할 수 없다.
                        if(!(bar[x+1][y-1]||bar[x+2][y-1]))
                            continue;
                    }
                    //왼쪽 보가 존재하는 경우
                    if(x>0&&plate[x-1][y]){
                        //왼쪽 보의 양 끝에 기둥이 존재하지 않는다면 x,y보를 삭제할 수 없다.
                        if(!(bar[x-1][y-1]||bar[x][y-1]))
                            continue;
                    }
                    plate[x][y]=false;
                }

            }else{
                //insert
                if(isBar==0){
                    //겹치도록 설치되는 경우는 없고, 바닥에선 무조건 설치할 수 있으니 설치한다.
                    if(y==0)
                        bar[x][y]=true;
                    else{
                        //설치할 위치의 왼쪽 보의 오른쪽 끝에 위치한다면 1번 조건에 의해 무조건 설치할 수 있다.
                        if(x>0&&plate[x-1][y])
                            bar[x][y]=true;
                        //설치할 위치의 보의 왼쪽 끝에 위차하기에 설치할 수 있다.
                        if(plate[x][y])
                            bar[x][y]=true;
                        //아래에 기둥이 있기에 설치할 수 있다.
                        if(bar[x][y-1])
                            bar[x][y]=true;
                    }
                }else{
                    //양 끝 밑에 기둥이 있다면 설치할 수 있다.
                    if(bar[x+1][y-1]||bar[x][y-1])
                        plate[x][y]=true;
                    //양 끝이 다른 보와 맞닿아 있다면 설치할 수 있다.
                    if((x>0&&plate[x-1][y])&&plate[x+1][y])
                        plate[x][y]=true;
                }

            }
        }
        List<int[]> ansList=new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if(bar[i][j]){
                    ansList.add(new int[]{i,j,0});
                }
                if(plate[i][j])
                    ansList.add(new int[]{i,j,1});
            }
        }
//        System.out.println("ansList.size() = " + ansList.size());
        return ansList.stream().toArray(int[][]::new);
    }
}

케이스를 나눠 쭉 풀어내는 문제였다.

몇번 제출을 해도 점수가 많이 낮아 다른 풀이들을 보니, 주로 삭제는 전체 배열에 대해 다시 설치할 수 있는지 검사하는 방식으로 검사를 했었다.

 

근데, 굳이 전체를 검사할 필요가 없는 문제라고 생각했고 세워둔 케이스를 제외하곤 다른 케이스가 존재하지 않는다고 판단하여

삭제 로직부터 천천히 다시 들여다보았다.

그러다 보니, 자연스레 문제를 찾았다.

보는 기둥의 위에 설치되어야 하는데, 보를 삭제하는 3,4번째 조건문에서 기둥을 체크하는 부분에서 보와 같은 y값을 가지는 기둥에 대해서 비교를 했었다..

해당 부분을 고치니 바로 통과가 되었다.

꽤 오래 삽질했던 문제라 상당히 허무했다..