[JS] 기둥과 보 설치

문제

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

프로그래머스

 

풀이

해당 문제는 각 기둥과 보의 설치/삭제에 대한 조건이 까다로운 문제이다. 나머지는 그닥 어려운 문제는 아니다.

 

우선 기둥의 설치부터 살펴보자.

문제에서 기둥이 설치될 수 있는 조건을 아래와 같이 정의했다.

1. 기둥은 y가 0인 바닥일 때
2. 다른 기둥의 위일때
3. 보의 양끝(왼쪽 오른쪽)일때

그렇다면 4가지 이외의 설치는 안된다는 것이다. 이를 이용해 기둥를 설치할 수 있는지 판별하는 함수를 만들어 주자.

 

그리고 보의 설치에 대한 조건을 알아보자.

문제에서 이야기한 보가 설치될 수 있는 조건은 아래와 같다.

1. 보의 양 끝중 한 부분이 기둥의 위에 위치할 때
2. 보의 양 끝이 다른 보 2개와 연결되어 있을 때

그렇다면 3가지 조건 이외의 상황에서는 보를 설치할 수 없다는 것이다. 이 부분 또한 보를 설치할 수 있는지 판별하는 함수를 만들어 주자.

 

마지막으로 삭제하는 작업을 알아보자.

삭제의 경우 문제에서는 해당 기둥 혹은 보를 삭제했을 때, 건축물의 요소들 중 설치 조건에 부합한 경우가 나오면 삭제 하지 않는다고 설명하고 있다.

그렇다면 우리가 순차적으로 작업하고 있는 결과물을 받아와 삭제하고자 하는 요소를 삭제하고 건축물 전체에 유효성 검사를 진행하면 된다. 이는 위에서 만든 설치 유효 판별 함수를 이용해 진행할 수 있다.

 

코드

const solution = (n, build_frame) => {
  const map = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => -1)
  );
  const answer = [];

  const checkFrame = (ary, x, y) => {
    if (y === 0) return true;
    else if (ary.find(([ax, ay, aa]) => ax === x && ay === y - 1 && aa === 0))
      return true;
    else if (ary.find(([ax, ay, aa]) => ax === x && ay === y && aa === 1))
      return true;
    else if (ary.find(([ax, ay, aa]) => ax === x - 1 && ay === y && aa === 1))
      return true;
    else return false;
  };

  const checkBoard = (ary, x, y) => {
    if (ary.find(([ax, ay, aa]) => ax === x && ay === y - 1 && aa === 0))
      return true;
    else if (
      ary.find(([ax, ay, aa]) => ax === x + 1 && ay === y - 1 && aa === 0)
    )
      return true;
    else if (
      ary.find(([ax, ay, aa]) => ax === x - 1 && ay === y && aa === 1) &&
      ary.find(([ax, ay, aa]) => ax === x + 1 && ay === y && aa === 1)
    )
      return true;
    else return false;
  };

  const destroy = (ary, x, y, type) => {
    const copyAry = [];
    for (let e of ary) {
      copyAry.push(e);
    }
    const idx = copyAry.findIndex(
      ([ox, oy, oa]) => ox === x && oy === y && oa === type
    );
    copyAry.splice(idx, 1);

    for (let [cx, cy, ca] of copyAry) {
      if (ca === 0 && !checkFrame(copyAry, cx, cy)) return;
      else if (ca === 1 && !checkBoard(copyAry, cx, cy)) return;
    }
    ary.splice(idx, 1);
  };

  for (let [x, y, a, b] of build_frame) {
    // 삭제
    if (b === 0) {
      destroy(answer, x, y, a);
    }
    // 생성
    else {
      // 보
      if (a === 0 && checkFrame(answer, x, y)) {
        answer.push([x, y, a]);
      }
      // 기둥
      else if (a === 1 && checkBoard(answer, x, y)) {
        answer.push([x, y, a]);
      }
    }
  }
  return answer.sort((a, b) => {
    if (a[0] === b[0]) {
      if (a[1] === b[1]) return a[2] - b[2];
      else return a[1] - b[1];
    } else return a[0] - b[0];
  });
};