(javascript) 기둥과 보 설치

https://school.programmers.co.kr/learn/courses/30/lessons/60061?language=javascript

프로그래머스

 

아주 머리가 아픈 문제였다

 

별다른 알고리즘이나 자료구조를 사용할 필요는 없고, 요구사항만 잘 구현하면 되는 문제였다.

 

요구사항은 주어진 명령어 배열 build_frame에서 명령을 하나씩 읽어와 수행하고, 마지막 결과를 반환하면 되는 간단한 내용이다.

build_frame은 [x, y, a, b] 형태로 주어지는데, x, y는 명령을 수행할 위치, a는 설치할 구조물의 종류(0 = 기둥, 1 = 보), b는 수행할 명령(0 = 제거, 1 = 설치)이다.

 

먼저 구조물을 시뮬레이션할 3차원 배열 frame을 만든다.

var frame = Array.from({ length: n + 1 }, 
    () => Array.from({ length: n + 1 }, 
        () => Array(2).fill(false)
    )
);

frame은 n*n 크기의 배열로, 초기값으로 [false, false]를 가진다.

첫번째 요소는 x, y에 기둥이 있는지를 나타내고, 두번째 요소는 x, y에 보가 있는지를 나타낸다.

 

build_frame에서 명령을 하나씩 불러와 수행한다.

명령을 수행할 때 도움을 받을 함수 isValid를 구현했다.

 

isValid는 frame에서 x, y,에 a가 유효한지를 검사하는 함수이다.

만약 a가 0이라면(기둥), y가 0이거나(바닥에 있음), x, y-1에 기둥이 있거나(지지해주는 기둥이 있음), x-1, y나 x, y에 보가 있어야한다(왼쪽이나 오른쪽을 지지해주는 보가 있어야함)

만약 a가 1이라면(보), x, y-1이나 x+1, y-1에 기둥이 있거나(왼쪽이나 오른쪽을 지지해주는 기둥이 있음), x-1, y와 x+1, y에 보가 있어야한다(양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야함)

 

위의 조건을 만족한다면 true를, 그렇지 않다면 false를 반환한다.

 

build_frame의 각 명령에 대해서, 만약 b = 1이라면(설치) isValid(x, y, a)를 시도해보고, true라면 설치하고 false라면 설치하지 않는다.

만약 b = 0이라면(제거) 또 다양한 조건을 살펴봐야한다.

만약 a = 0이라면(기둥) 우선 x, y에서 기둥을 제거한다. x, y에서 기둥을 제거한다면 x-1, y+1의 보, x, y+1의 기둥, x, y+1의 보가 영향을 받는다. 만약 각각이 존재하고, isValid를 통과하지 못한다면 이 명령은 유효하지 않다. 그러므로 작업을 되돌린다.

a = 1(보)일때도 마찬가지로 우선 x, y에서 보를 제거한다. x, y에서 보를 제거한다면 x-1, y의 보, x, y의 기둥, x+1, y의 보, x+1, y의 기둥이 영향을 받는다. 만약 각각이 존재하고, isValid를 통과하지 못한다면 이 명령은 유효하지 않다. 그러므로 작업을 되돌린다.

 

이 과정에서 x와 y가 유효한 범위 안에 있는지도 확인해줘야한다. 만약 x = 0일 때 기둥을 제거하려 한다면 frame[x-1][y]에 접근하려해 런타임 에러가 발생할 것이다.

 

코드

function solution(n, build_frame) {
    var answer = [];
    // answer : [x, y, a]
    // x, y : 위치
    // a : 구조물 종류

    // 최대 20000B -> 20KB
    var frame = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => Array(2).fill(false)));

    for (var i = 0; i < build_frame.length; i++) {
        var [x, y, a, b] = build_frame[i];
        // x, y : 위치
        // a : 0은 기둥, 1은 보
        // b : 0은 삭제, 1은 설치

        // 각 작업을 수행한 후, 조건에 맞는지 확인
        if (b === 1) {
            // 설치
            if (isValid(frame, x, y, a)) {
                frame[x][y][a] = true;
            }
        } else if (b === 0) {
            // 삭제
            // 기둥
            if (a === 0) {
                // 일단 빼
                frame[x][y][a] = false;
                // 뺐더니 유효하지 않아
                if (!(!frame[x][y + 1][0] || isValid(frame, x, y + 1, 0))
                    ||
                    (0 < x && !(!frame[x - 1][y + 1][1] || isValid(frame, x - 1, y + 1, 1)))
                    ||
                    !(!frame[x][y + 1][1] || isValid(frame, x, y + 1, 1))
                ) {
                    // 그럼 되돌려
                    frame[x][y][0] = true;
                }
            } else if (a === 1) {
                frame[x][y][a] = false;
                if ((0 < x && !(!frame[x - 1][y][1] || isValid(frame, x - 1, y, 1)))
                    ||
                    !(!frame[x][y][0] || isValid(frame, x, y, 0))
                    ||
                    !(!frame[x + 1][y][1] || isValid(frame, x + 1, y, 1))
                    ||
                    !(!frame[x + 1][y][0] || isValid(frame, x + 1, y, 0))
                ) {
                    frame[x][y][1] = true;
                }
            }
        }
    }

    for (var i = 0; i < frame.length; i++) {
        for (var j = 0; j < frame[0].length; j++) {
            if (frame[i][j][0]) {
                answer.push([i, j, 0]);
            }
            if (frame[i][j][1]) {
                answer.push([i, j, 1]);
            }
        }
    }
    return answer;
}

// frame에서 어떤 지점 x, y에 a를 놓을 수 있는지 확인하는 함수
const isValid = (frame, x, y, a) => {
    // 기둥
    if (a === 0) {
        // y === 0이거나, x, y-1에 기둥이 있거나, x-1, y에 보가 있거나, x, y에 보가 있어야함
        if (y === 0 || frame[x][y - 1][0] || (0 < x && frame[x - 1][y][1]) || frame[x][y][1]) {
            return true;
        }
    }
    // 보
    else if (a === 1) {
        // x, y-1에 기둥이 있거나, x+1, y-1에 기둥이 있거나, x-1, y와 x+1, y에 보가 있어야함
        if (frame[x][y - 1][0] || frame[x + 1][y - 1][0] || (0 < x && frame[x - 1][y][1] && frame[x + 1][y][1])) {
            return true;
        }
    }
    return false;
}

 

후기

 처음에는 외부 함수 isValid없이 solution 내부에서 모든 조건문과 검사를 수행하려 했다. 몇시간동안 씨름해서 어느정도 작업을 완료했을 때, 코드가 너무 더럽고, 읽기 힘들다는 것을 발견했다. 그래서 isValid 함수를 외부로 빼서 따로 구현하기로 했다.

 여전히 코드가 더럽지만 이전보다는 훨씬 낫다고 할 수 있다. 그리고 구조물 제거 명령에 대해서도 추가적인 외부 함수를 작성해서 더 코드를 깔끔하게 작성할 수 있을 것 같다.