[프로그래머스]기둥과 보 설치 - JAVA

문제

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

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

풀이

구현/시뮬레이션 문제이다. 각각의 동작을 따로따로 생각하고 분리하여 풀면 쉽지만 처음에는 굉장히 어렵게 느껴졌다.

 

pillar와 bar가 겹치게 되면 계산하기 어려우므로 기둥 따로, 보 따로 존재하는지 알 수 있는 배열을 boolean으로 만들어 주었다. 그리고 정답을 반환할 때 이 둘을 합쳐주었고, 이때 반환할 정답 배열의 크기를 지정해 주기 위해 기둥과 보를 설치, 삭제할 때마다 카운팅을 해주었다.

 

다음과 같은 과정으로 나누어서 풀면 된다

1. 기둥을 설치한다.

2. 기둥을 삭제한다.

3. 보를 설치한다.

4. 보를 삭제한다.

5. 결과를 담은 배열을 만들어 반환한다.

먼저 1, 3번 과정부터 살펴보쟝.

설치할 때는 해당 위치에 기둥이나 보를 설치할 수 있는지 확인하고 설치해 주면 된다. 

기둥을 설치할 때에는 기둥이 바닥에 있거나, 보의 한쪽 끝 위이거나, 또 다른 기둥 위에 있으면 된다.

보를 설치할 때에는 보의 한쪽 끝이 기둥이거나, 보의 양쪽 끝이 동시에 다른 보와 연결되어야 한다.

그리고 설치할 때마다 count++를 해준다.

 

2. 4번 과정은 삭제하는 과정이다.

일단 삭제를 하고 canDelete를 통해 삭제를 한 후에도 기둥과 보가 유효한 위치에 있는지 확인하면 된다. 삭제한 후에 유효하지 않는 기둥과 보가 있다면 다시 설치를 해주면 되고, 아니면 count--를 해서 완벽하게 삭제해 주면 된다.

canDelete는 범위 내의 모든 기둥, 보가 문제 조건에 맞는 위치에 있는지 확인하고, 하나라도 조건에 맞는 위치에 없다면 false를 반환한다.

 

마지막 5번이다. 앞에서 계산하면서 기둥, 보의 개수를 카운팅 해주었기 때문에 result배열을 쉽게 만들 수 있다.

모든 범위를 돌면서 기둥이 있다면 해당 위치에 기둥이 있다고 result배열에 저장해주고, 보가 있다면 해당 위치에 보가 있다고 저장해 주면 된다.

코드

class Solution {
    
    boolean[][] pillar;
    boolean[][] bar;
    
    public int[][] solution(int n, int[][] build_frame) {
        pillar = new boolean[n + 1][n + 1];
        bar = new boolean[n + 1][n + 1];
        
        int count = 0;
        for(int i = 0; i < build_frame.length; i++) {
            int x = build_frame[i][0];
            int y = build_frame[i][1];
            int type = build_frame[i][2];
            int action = build_frame[i][3];
            
            if(type == 0) { //기둥을
                if(action == 1) { //설치한다
                    if(checkPillar(x, y)) {
                        pillar[x][y] = true;
                        count++;
                    }  
                } else { //삭제한다
                    pillar[x][y] = false;
                    if(canDelete(n) == false) pillar[x][y] = true;
                    else count--;
                }
            } else { //보를
                if(action == 1) {
                    if(checkBar(x, y)) { //설치한다
                        bar[x][y] = true;
                        count++;
                    } 
                } else { //삭제한다
                    bar[x][y] = false;
                    if(canDelete(n) == false) bar[x][y] = true;
                    else count--;
                }
            }
        }
        
        int[][] result = new int[count][3];
        int idx = 0;
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= n; j++) {
                if(pillar[i][j]) {
                    result[idx][0] = i;
                    result[idx][1] = j; 
                    result[idx++][2] = 0;
                }
                if(bar[i][j]) {
                    result[idx][0] = i;
                    result[idx][1] = j;
                    result[idx++][2] = 1;
                }
            }
        }
        return result;
    }
    
    public boolean canDelete(int n) {    
        for(int i = 0; i <= n; i++) { 
            for(int j = 0; j <= n; j++) { 
                if(pillar[i][j] && checkPillar(i, j) == false)  return false; // 기둥이 해당 위치에 있을 수 없다면 false 
                else if(bar[i][j] && checkBar(i, j) == false) return false; // 바닥이 해당 위치에 있을 수 없다면 false 
            }
        }
        return true;
    }
    
    public boolean checkPillar(int x, int y) {
        if(y == 0) return true; //바닥에 설치하는 경우
        else if(y > 0 && pillar[x][y - 1]) return true; //아래 기둥이 있는 경우
        else if(x > 0 && bar[x - 1][y] || bar[x][y]) return true;
        return false;
    }
    
    public boolean checkBar(int x, int y) {
        if(y > 0 && pillar[x][y - 1] || pillar[x + 1][y - 1]) return true; // 한쪽 끝에 기둥이 있는 경우
        else if(x > 0 && bar[x - 1][y] && bar[x + 1][y]) return true; //양쪽 끝이 보와 동시에 연결되어 있는 경우
        return false;
    }
}