[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 기둥과 보 설치 (Java)

 

 

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

코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스

 

 

2020 카카오 공채의 5번째 문제 기둥과 보 문제다.

예전에 문제 한번 읽어보고 감이 오지 않아서 접어두었던 문젠데, 어제 가사 검색을 풀고 자신감이 생겨서 한번 풀어보게 되었다.

 

기둥과 보를 세우거나 제거하면서 남아 있는 구조물의 상태를 출력하는 문제다.

기둥과 보를 세울 때는 다음과 같은 규칙을 가진다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

어떤 구조물을 삭제할 때는 삭제된 구조물을 제외하고 나머지 구조물들이 위의 조건을 만족해야 한다.

 

이번 문제에서는 기둥과 보의 상태를 나타내는 2차원 boolean 배열 2개를 사용했다.

기둥과 보가 동시에 같은 위치에 있을 수 있으므로 구분해주기 위함이다.

배열의 크기는 n + 3으로 정했다.

n = 5라고 하면, 구조물들의 위치가 0~5까지 있을 수 있으므로 +1을 해준다.

또한, 규칙에서 보는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 하므로

(0, y) 위치에 있는 보를 삭제할 때 -1 위치를 제외해주기 양쪽에 각각 1씩 더해서 총 +3을 해주게 되었다.

따라서 배열은 1부터 n+1의 인덱스만 사용하게 된다.

 

 

함수는 총 3가지를 구현했다.

위의 두 규칙을 구현한 isExistCol, isExistRow 함수와 구조물을 삭제할 수 있는지 판단하는 canRemove 함수다.

canRemove 함수에서 생각한 로직은 다음과 같다.

우선 삭제할 위치의 구조물을 삭제한다.

그 후, 남아 있는 모든 구조물들을 체크하여 위의 두 규칙을 여전히 만족하는지를 판단한다.

삭제한 구조물은 원상복구 시키고, 하나라도 위의 규칙을 만족하지 못한다면 false를, 모든 구조물들이 만족한다면 true를 리턴한다.

true를 리턴 받았으면 해당 위치의 구조물을 삭제한다.

 

이전에 이 문제를 봤을 때는 삭제하는 부분이 까다로워서 해결을 하지 못했었다.

어떤 한 구조물을 삭제하기 전에 주변의 구조물이 살아남는지를 판단했었는데,

이런 식으로 생각을 하니 체크해야 할 부분이 너무 많고 복잡해서 전혀 감이 오질 않았다.

그래서 삭제를 먼저 한 뒤, 모든 구조물을 탐색하여 여전히 살아 있는지를 체크하게 되었다.

남아 있는 구조물들을 체크할 때 그냥 맵 전체를 탐색하며 구조물인 것을 체크했는데,

건물을 세울 때 구조물의 위치를 ArrayList에 따로 저장하여 그 부분만 탐색하면 시간을 더욱 절약할 수 있을 듯 하다.

하지만 효율성 체크를 하지 않는 문제라서 하지 않았다. (귀찮)

 

 

총 걸린 시간 : 1시간

난이도 : ★★★☆☆

 

코드

class Solution {
    private int n;
    private boolean[][] cols, rows; // 기둥, 보
    private final int COLUMN = 0, ROW = 1, REMOVE = 0, ADD = 1;

    public int[][] solution(int n, int[][] build_frame) {
        this.n = n;
        int count = 0;
        cols = new boolean[n + 3][n + 3];
        rows = new boolean[n + 3][n + 3];

        for (int[] frame : build_frame) {
            int x = frame[0] + 1;
            int y = frame[1] + 1;
            if (frame[2] == COLUMN) { // 기둥
                if (frame[3] == ADD && isExistCol(x, y)) { // 해당 위치에 기둥을 세울 수 있으면
                    cols[x][y] = true;
                    count++;
                }
                if (frame[3] == REMOVE && canRemove(x, y, COLUMN)) { // 삭제할 수 있으면
                    cols[x][y] = false;
                    count--;
                }
            } else { // 보
                if (frame[3] == ADD && isExistRow(x, y)) {
                    rows[x][y] = true;
                    count++;
                }
                if (frame[3] == REMOVE && canRemove(x, y, ROW)) {
                    rows[x][y] = false;
                    count--;
                }
            }
        }

        int[][] answer = new int[count][3];
        int index = 0;
        for (int i = 1; i <= n + 1; i++) { // 남아 있는 기둥과 보 배열에 저장
            for (int j = 1; j <= n + 1; j++) {
                if (cols[i][j]) answer[index++] = new int[]{i - 1, j - 1, COLUMN};
                if (rows[i][j]) answer[index++] = new int[]{i - 1, j - 1, ROW};
            }
        }
        return answer;
    }

    private boolean isExistCol(int x, int y) { // x, y 위치에 존재할 수 있는지
        return y == 1 || cols[x][y - 1] || rows[x][y] || rows[x - 1][y];
    }

    private boolean isExistRow(int x, int y) {
        return cols[x][y - 1] || cols[x + 1][y - 1] || (rows[x - 1][y] && rows[x + 1][y]);
    }

    private boolean canRemove(int x, int y, int type) {
        boolean result = true;

        if (type == COLUMN) cols[x][y] = false; // 임시로 삭제
        else rows[x][y] = false;

        loop:
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (cols[i][j] && !isExistCol(i, j)) {
                    result = false;
                    break loop;
                }
                if (rows[i][j] && !isExistRow(i, j)) {
                    result = false;
                    break loop;
                }
            }
        }

        if (type == COLUMN) cols[x][y] = true; // 삭제했던 구조물 원상복구
        else rows[x][y] = true;

        return result;
    }
}