[프로그래머스] 기둥과 보 설치 (java)

코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 기둥과 보 설치

어떻게 생각하고 문제를 풀었는가?

기둥을 설치하기 위한 조건은 다음과 같습니다.

1. 설치하려는 위치가 바닥이다.
2. 한 칸 아래에 기둥이 있다.
3. 한 칸 아래에 좌측에서부터 펼쳐진 보가 있다.

우측을 펼쳐지는 보를 설치하기 위한 조건은 다음과 같습니다.

1. 한 칸 아래에 기둥이 있다.
2. 한 칸 아래, 한 칸 오른쪽에 기둥이 있다.
3. 한 칸 왼쪽과 한 칸 오른쪽 모두 보가 펼쳐져 있다.

기둥과 보를 삭제할 때 연결된 기둥 혹은 보가 설치 조건을 만족하지 못한다면 삭제는 이루어지지 않습니다.

삭제를 먼저 수행하고 난 후 모든 기둥과 보에 대해서 설치 조건을 만족하는지 않았을 때 삭제를 되돌린다면 삭제에 대해서도 정상적으로 수행할 수 있을 것이라고 생각하였습니다.

코드

import java.util.*;

class Solution {
    private boolean[][] pillars;
    private boolean[][] covers;
    
    public int[][] solution(int n, int[][] build_frame) {
        pillars = new boolean[n+3][n+3];
        covers = new boolean[n+3][n+3];
        for(int[] commands : build_frame){
            int x = commands[0]+1;
            int y = commands[1]+1;
            int type = commands[2];
            boolean isDelete = (commands[3]==0);
            if(isDelete){
                if(type==0){
                    pillars[x][y] = false;    
                }else{
                    covers[x][y] = false;
                }
                
                if(!canDestroy(x, y, n)){
                    if(type==0){
                        pillars[x][y] = true;
                    }else{
                        covers[x][y] = true;
                    }
                }
            }else{
                if(type==0 && checkPillar(x,y)){
                    pillars[x][y] = true;    
                }
                if(type==1 && checkCover(x,y)){
                    covers[x][y] = true;    
                } 
            }
        }

        ArrayList<int[]> results = new ArrayList<>();
        for(int i=1; i<=n+1; i++){
            for(int j=1; j<=n+1; j++){
                if(pillars[i][j]) results.add(new int[]{i-1, j-1, 0});
                if(covers[i][j]) results.add(new int[]{i-1, j-1, 1});
            }
        }
        int[][] answer = results.toArray(new int[0][0]);
        return answer;
    }
    
    private boolean checkPillar(int x, int y){
        return y==1 || pillars[x][y-1] || covers[x][y] || covers[x-1][y];
    }
    
    private boolean checkCover(int x, int y){
        return pillars[x][y-1] || pillars[x+1][y-1] || (covers[x+1][y] && covers[x-1][y]);
    }
    
    private boolean canDestroy(int x, int y, int n){
        for(int i=1; i<=n+1; i++){
            for(int j=1; j<=n+1; j++){
                if(pillars[i][j] && !checkPillar(i,j)) return false;
                if(covers[i][j] && !checkCover(i,j)) return false;
            }
        }
        return true;
    }
}

 

NxN 좌표에 기둥과 보의 설치를 표현하고, 설치/삭제시 조건을 체크하여 문제를 해결하였습니다.

코드를 작성함에 있어 주의해야할 점은 (x,y) 좌표에 기둥과 보가 동시에 설치되있을 수 있다는 점입니다.

저는 NxN 좌표에 설치된 기둥과 보를 pillars 배열과 covers 배열로 각각 표현함으로써 이러한 문제를 해결하였습니다.

또한 각 설치물의 설치 조건을 체크하는데 있어 벽면의 끝에 설치되는 경우를 고려해야합니다.

배열의 크기를 양옆으로 1칸씩 크게 초기화하여 체크한다면 이러한 문제를 피할 수 있습니다.