프로그래머스_기둥과 보 설치_60061

문제 링크

조건

• n : 2차원 벽면의 크기 (n x n), 범위는 5~100 이하의 자연수
• 기둥과 보를 설치(삭제)하는 데, 조건에 위배되면 설치(삭제) 작업명령을 무시함
  • 기둥 : 바닥 위 or 보의 한쪽 끝 부분 위 or 다른 기둥 위 에만 설치 가능
  • 보 : 한쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시에 연결된 경우에만 설치 가능
• 작업명령 배열 [x, y, a, b] : [가로좌표, 세로좌표, 구조물 종류, 설치or삭제] 로 주어짐

 

접근 방법

• 처음에 설치 시 구조물별 조건과 삭제 시 구조물별 조건을 따로 생각해 작업 명령에 따라 매번 조건을 확인하는 식으로 접근 => 테스트케이스 몇 개 씩 계속 틀림..
  • 문제에는 설치 시 조건만 나와있음
  • 구조물 삭제 시 조건에서 놓친 부분이 있어 테스트케이스를 계속 틀림..
  • 문제에 명확히 주어진 조건만 보고 풀이를 생각해 내야 함 => 분명 놓친 부분이 있을 것이기 때문에,,
• 문제에 나와있는 설치 시 조건만 가지고 솔루션 접근
  • 구조물 설치 시에는 주어진 설치 조건에 맞는지 확인
  • 구조물 삭제 시에는 해당 구조물을 지워놓고 벽면에 세워져 있는 모든 구조물이 설치 기준에 부합하는 지 확인(해당 구조물을 없애도 구조에 문제가 없는지 확인) => 전수 조사

 

솔루션

class Solution {
    boolean[][] pillar;
    boolean[][] bow;
    
    //기둥 설치 기준 체크
    public boolean checkPillar(int r, int c){
        if(r == 0 || pillar[r-1][c]){//바닥 위 || 기둥 위
            return true;
        }
        
        if((c > 0 && bow[r][c-1]) || bow[r][c]) return true;//보의 끝 부분 위
        
        return false;
    }
    
    //보 설치 기준 체크
    public boolean checkBo(int r, int c){
        if(r > 0 && (pillar[r-1][c] || pillar[r-1][c+1])){//한쪽 끝이 기둥 위
            return true;
        }
        if(c > 0 && bow[r][c-1] && bow[r][c+1]){//양쪽 끝이 다른 보와 동시에 연결
            return true;
        }
        return false;
    }
    
    //삭제 시 전수 조사
    public boolean deleteCheck(int n){
        for(int i = 0; i < n+1; i++){
            for(int j = 0; j < n+1; j++){
                if(bow[i][j]){
                    if(!checkBo(i,j)) return false;
                }
                if(pillar[i][j]){
                    if(!checkPillar(i,j)) return false;
                }
            }
        }
        return true;
    }
    
    public int[][] solution(int n, int[][] build_frame) {
        
        pillar = new boolean[n+5][n+5];
        bow = new boolean[n+5][n+5];
        
        int r,c,a,b;
        for(int i = 0, size = build_frame.length; i < size; i++){
            int[] cur = build_frame[i];
            c = cur[0];
            r = cur[1];
            a = cur[2];
            b = cur[3];
            
            if(b == 1){//설치
                if(a == 0){ //기둥
                    if(checkPillar(r,c)){
                        pillar[r][c] = true;//기둥
                        continue;
                    }
                }else{//보
                    if(checkBo(r,c)){
                        bow[r][c] = true;
                        continue;
                    }
                }
            }else{//삭제
                if(a == 0){//기둥
                    pillar[r][c] = false;
                    if(!deleteCheck(n)) pillar[r][c] = true;
                }else{//보
                    bow[r][c] = false;
                    if(!deleteCheck(n)) bow[r][c] = true;
                }
            }
        }
        
        List<int[]> list = new ArrayList<int[]>();
        
        for(int i = 0; i < n+1; i++){
            for(int j = 0; j < n+1; j++){
                if(pillar[j][i]) list.add(new int[]{i,j,0});
                if(bow[j][i]) list.add(new int[]{i,j,1});
            }
        }
        
        int[][] answer = list.toArray(new int[list.size()][]);
        
        return answer;
    }
}

 

 

리뷰

• 구조물 삭제 시 조건이 주어지지 않았더라도 설치 시 기준만 보고 조건을 모두 찾아서 걸러줄 수 있을거라 생각했지만 계속 놓치는 부분이 생김..
• 문제에 명확히 주어진 조건만 가지고 문제 풀이에 접근하는 연습을 해야할 듯!