[프로그래머스] 기둥과 보 설치 (Lv.3, 자바스크립트)

young_pallete·2022년 9월 22일

Algorithm

목록 보기

27/32

🌈 시작하며

사실 시간복잡도가 높지 않아서, 다른 야매(?) 방법으로 풀려 했는데, 최근 코테 스터디에서 다른 분의 푸시는 과정을 보고, 구현으로도 풀 수 있겠다는 영감을 얻어 풀어봤어요. 제가 워낙 하나하나 하드 코딩하는 것을 싫어하는 경향이 있는 터라, 이참에 좀 저를 갱생(?)시키자는 취지도 있었고요!

실제로 엣지 케이스들이 많아서 약 8시간이 걸렸지만, 그래도 뭔가 생각하는 힘을 기를 수 있어서 좋았습니다 🥰

그럼, 시작해볼까요? 😉

🚦 본론

구현 과정 도출

일단 알고리즘을 푸는 목적이 다양하겠지만, 저는 다양한 방법을 시도하려 노력하는 편이에요.
따라서 이번에는 받은 영감 그대로, 클래스로 한 번 풀어봤어요!

일단 먼저 문제에서 주어진 조건을 꼭! 봅시다.

기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

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

따라서, 일단 우리는 이에 대한 유효성 검사를 할 수 있는 함수를 짜야겠네요!
결국 이 문제의 큰 틀은

기둥인지 보인지를 판별

삭제인지, 추가인지를 판별

해당 명령이 유효한지를 판별

실제 배열에 렌더

렌더 함수에서 완성된 결과물을 결과 조건에 맞춰서 반환

인데요! 이때, 우리는 어떤 게 유효한 기둥, 보인가?를 고민해야 합니다.

어떤 게 유효한 기둥, 보인가?

일단 저는 시뮬레이션하는 전략을 선택했어요.
일단 추가하거나 삭제한 다음 ➡ 이게 유효한지를 검사해보는 거죠!

이후 우리는 조건을 상세히 전개해주어야 하는데요. 추가 시에는 위의 조건과 일치합니다.

하지만 고민되는 게 있는데요. 바로 삭제 조건입니다!

왜냐하면, 삭제를 한다면 다음과 같은 까다로운 조건들이 존재하기 때문입니다.

기둥을 삭제한다면

다음과 같은 요소들이 기둥의 삭제로 인해 유효하지 않을 수 있게 돼요!

내 위치 바로 위의 기둥: 만약 보가 없다면 해당 건축물은 유효하지 않을 수 있겠군요!
내 위치의 바로 위의 보: 현재 위치의 바로 위의 보가 이 기둥만을 의지할 수도 있습니다.
내 위치의 왼쪽 위 대각선의 보: 내 왼쪽 위 대각선의 보가 오직 이 기둥만을 의지하고 있다면, 유효하지 않겠죠?

따라서 이에 대한 유효성 검사를 추가로 해줘야겠죠? 😉

보를 삭제한다면

보는 다음과 같은 영향을 미칠 수 있어요!

내 왼쪽의 보: 만약 양쪽으로 보가 의지해주기에 가능했다면, 유효하지 않아요!
내 오른쪽의 보: 마찬가지입니다!
내 위치의 기둥: 이 기둥이 해당 보에 크게 의존할 수도 있겠죠?
내 오른쪽 위치의 기둥: 보는 현재 위치에서 오른쪽으로 전개됩니다. 따라서 해당 기둥도 이 보에 의지할 수 있습니다!

따라서 이러한 조건들을 하나하나 체크해주는 과정이 필요하겠어요!

정리

그렇다면 우리는 구현과정을 다음과 같이 도출할 수 있겠습니다.

기둥인지 보인지를 판별

삭제인지, 추가인지를 판별

해당 명령이 유효한지를 판별. 이때, 일단 유효하다는 가정하에 먼저 업데이트하고, 유효성 검사가 완료되면 원래대로 되돌리는 방식을 채택.
3-1. 기둥, 보의 추가가 유효한지를 판별하는 체크 함수 구현
3-2. 기둥의 삭제가 유효한지를 판별하는 체크 함수 구현
3-3. 보의 삭제가 유효한지를 판별하는 체크 함수 구현

만약 유효하다면 실제 배열에 렌더

렌더 함수에서 완성된 결과물을 결과 조건에 맞춰서 반환

그렇다면, 이제 구현을 해봅시다!

구현

구현은 클래스를 기반으로 만들었어요!

메인 함수 및 클래스 구현

먼저 예상되는 메서드와 메인 함수 코드들을 간단하게 써놓읍시다!

class BuildMap {
  constructor(n) {
    this.mapSize = n + 1;
    this.arr = Array.from(
      { length: this.mapSize },
      () => Array.from({ length: this.mapSize }, () => [false, false])
    );
  }
  
  render(buildFrame) {} // 실제 맵 랜더링 함수

  getFinalBuildMaterials() {} // 필요한 건축물을 결과 조건에 맞게 반환
}

const solution = (n, buildFrame) => {
  const buildMap = new BuildMap(n);
  buildMap.render(buildFrame);

  return buildMap.getFinalBuildMaterials();
};

1. 기둥인지 보인지를 판별

저는 private class field를 이번에 한 번 써봤어요! (아직도 낯설군요. 크흡)

class BuildMap {
  #PILLAR_CODE = 0;
  #FLOOR_CODE = 1;
  
  #BuildTypes = Object.freeze({
    [this.#PILLAR_CODE]: '기둥',
    [this.#FLOOR_CODE]: '보',
  }); // readonly하도록 설정.
}

2. 삭제인지 추가인지를 판별

약간 의아할 수 있겠는데, 왜 저렇게 객체를 굳이 또 따로 추가로 들여서 새로운 값을 생성하지?라는 생각이 들 수 있겠네요.

이유는 코딩 테스트 상에서는 아무 문제가 없지만 제게 다음과 같은 이유가 있기에 그냥 객체로 한 번 할당 받아서 썼어요!

아무래도 0과 1이라는 이름이 누군가에게 설명하기 막연할 수도 있다고 생각했어요.
이게 코테에서는 큰 상관이 없지만, 실제로는 해당 명령 코드가 바뀔 수도 있겠죠? 그렇다면 관련된 0과 1이라는 코드를 모두 바꿔줘야 합니다. 이때, 0과 1이 기둥, 보의 코드와 일치하므로, 다른 개발자가 유지보수하기 매우 불편한 상황이 존재할 수 있어요. 따라서 일종의 매직넘버로 제가 해당 코드들을 객체에서 한 번 치환해준 겁니다! (나중에 제가 디버깅하기에도 매우 용이한 것도 있구요!)

class BuildMap {
  ...
  #COMMAND_ADD_CODE = 1;
  #COMMAND_DELETE_CODE = 0;
  
  #CommandTypes = Object.freeze({
    [this.#COMMAND_DELETE_CODE]: '삭제',
    [this.#COMMAND_ADD_CODE]: '추가',
  });
}

3. 해당 명령이 유효한지를 판별

이제 우리는 각각의 상황에 맞춰서 그냥 명령을 쏴내려주는 함수를 구현하면 됩니다!

  checkBuild(x, y, buildType, commandType) {
    const commands = {
      [this.#CommandTypes[this.#COMMAND_DELETE_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]:
          this.checkDeletePillarPossible.bind(this, x, y),
        [this.#BuildTypes[this.#FLOOR_CODE]]:
          this.checkDeleteFloorPossible.bind(this, x, y),
      },
      [this.#CommandTypes[this.#COMMAND_ADD_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]: this.possibleAdd.bind(
          this,
          x,
          y,
          this.#PILLAR_CODE
        ),
        [this.#BuildTypes[this.#FLOOR_CODE]]: this.possibleAdd.bind(
          this,
          x,
          y,
          this.#FLOOR_CODE
        ),
      },
    };

    return commands[commandType][buildType]();
  }

3-1. 기둥의 추가가 유효한지를 판별하는 체크 함수 구현

기존의 문제 조건에 부합한지를 체크하는 isValidPillar, isValidFloor를 구현시키고, 타입에 맞춰 이를 호출하며 체크하는 possibleAdd를 구현했습니다.

  isValidPillar(x, y) {
    if (x < 0) return false;
    if (y < 0) return false;

    // 바닥에 설치할 경우
    if (y === 0) return true;

    // 한쪽 보 끝에 위치할 경우
    if (this.arr[x][y][1]) return true;
    if (x > 0 && this.arr[x - 1][y][1]) return true;

    // 다른 기둥 위에 있을 경우
    if (this.arr[x][y - 1][0]) return true;

    return false;
  }

  isValidFloor(x, y) {
    if (x < 0 || x >= this.mapSize - 1) return false;
    if (y <= 0) return false;

    // 한쪽 끝 부분이 기둥 위에 있는 경우
    if (this.arr[x][y - 1][this.#PILLAR_CODE]) return true;
    if (this.arr[x + 1][y - 1][this.#PILLAR_CODE]) return true;

    // 다른 보와 동시에 연결되어 있을 경우
    if (
      x &&
      this.arr[x - 1][y][this.#FLOOR_CODE] &&
      this.arr[x + 1][y][this.#FLOOR_CODE]
    )
      return true;

    return false;
  }

  possibleAdd(x, y, buildTypeCode) {
    if (this.arr[x][y][buildTypeCode]) return false;

    this.arr[x][y][buildTypeCode] = true;

    const result = buildTypeCode
      ? this.isValidFloor(x, y)
      : this.isValidPillar(x, y);

    this.arr[x][y][buildTypeCode] = false;

    return result;
  }

3-2. 기둥의 삭제가 유효한지를 판별하는 체크 함수 구현

시뮬레이션을 위해 일단 삭제하는 delete와, 마지막에는 복구하는 backupBeforeUpdate까지 추가로 구현해야 해요!

  delete(x, y, buildCode) {
    this.arr[x][y][buildCode] = false;
  }

  backupBeforeDelete(x, y, buildCode) {
    this.arr[x][y][buildCode] = true;
  }

  checkDeletePillarPossible(x, y) {
    if (!this.arr[x][y][this.#PILLAR_CODE]) return false;

    this.delete(x, y, this.#PILLAR_CODE);

    // pillar
    // 내 위에 기둥이 있을 경우.
    const overPillarStandPossible =
      y + 1 >= this.mapSize ||
      !this.arr[x][y + 1][this.#PILLAR_CODE] ||
      this.isValidPillar(x, y + 1);

    // 위쪽의 보가 없거나, 지탱할 만한 뭔가가 있어야 한다.
    const nowOverFloorStandPossible =
      y + 1 >= this.mapSize ||
      !this.arr[x][y + 1][1] ||
      this.isValidFloor(x, y + 1);

    // 왼쪽 보도 없거나, 버틸 수만 있다면 가능.
    const nowOverLeftFloorStandPossible =
      x - 1 < 0 ||
      y + 1 >= this.mapSize ||
      !this.arr[x - 1][y + 1][this.#FLOOR_CODE] ||
      this.isValidFloor(x - 1, y + 1);

    const result =
      overPillarStandPossible &&
      nowOverFloorStandPossible &&
      nowOverLeftFloorStandPossible;

    this.backupBeforeDelete(x, y, this.#PILLAR_CODE);

    return result;
  }

3-3. 보의 삭제가 유효한지를 판별하는 체크 함수 구현

마찬가지로 보의 삭제 체크도 구현!

```checkDeleteFloorPossible(x, y) {
    if (!this.arr[x][y][1]) return false;

    this.delete(x, y, this.#FLOOR_CODE);

    // floor
    // 만약 현재 위치에 기둥이 있다면 유효한지 체크
    const isPillarStandPossible =
      !this.arr[x][y][this.#PILLAR_CODE] || this.isValidPillar(x, y);

    // 현재의 오른쪽에 세워진 기둥도 유효한지 체크.
    const isRightPillarStandPossible =
      x + 1 >= this.mapSize ||
      !this.arr[x + 1][y][this.#PILLAR_CODE] ||
      this.isValidPillar(x + 1, y);

    // 현재의 왼쪽 보도 유효한지 체크
    const isLeftFloorStandPossible =
      x - 1 < 0 ||
      !this.arr[x - 1][y][this.#FLOOR_CODE] ||
      this.isValidFloor(x - 1, y);

    // 현재의 오른쪽 보도 유효한지 체크
    const isRightFloorStandPossible =
      x + 1 >= this.mapSize ||
      !this.arr[x + 1][y][this.#FLOOR_CODE] ||
      this.isValidFloor(x + 1, y);

    const result =
      isPillarStandPossible &&
      isRightPillarStandPossible &&
      isLeftFloorStandPossible &&
      isRightFloorStandPossible;

    this.backupBeforeDelete(x, y, this.#FLOOR_CODE);

    return result;
  }

4. 만약 유효하다면 실제 배열에 렌더

여기서는 렌더 함수를 만드는데, 체크가 완료되면 만약 유효하면 update가 되도로 해주었어요!

  updateBuildMap(x, y, buildCode, commandCode) {
    // 0 = delete => false, 1 = add => true
    this.arr[x][y][buildCode] = !!commandCode;
  }

  render(buildFrame) {
    buildFrame.forEach((command) => {
      const [x, y, buildCode, commandCode] = command;

      if (
        this.checkBuild(
          x,
          y,
          this.#BuildTypes[buildCode],
          this.#CommandTypes[commandCode]
        )
      ) {
        this.updateBuildMap(x, y, buildCode, commandCode);
      }
    });
  }

5. 렌더 함수에서 완성된 결과물을 결과 조건에 맞춰서 반환

정렬 조건에 맞게, for문을 돌려 맞춤으로 생성한 배열을 반환해요!

  getFinalBuildMaterials() {
    const buildMaterials = [];

    for (let i = 0; i < this.mapSize; i += 1) {
      for (let j = 0; j < this.mapSize; j += 1) {
        for (let buildCode = 0; buildCode < 2; buildCode += 1) {
          if (this.arr[i][j][buildCode]) {
            buildMaterials.push([i, j, buildCode]);
          }
        }
      }
    }

    return buildMaterials;
  }

전체 코드

class BuildMap {
  #PILLAR_CODE = 0;
  #FLOOR_CODE = 1;
  #COMMAND_ADD_CODE = 1;
  #COMMAND_DELETE_CODE = 0;

  #BuildTypes = Object.freeze({
    [this.#PILLAR_CODE]: '기둥',
    [this.#FLOOR_CODE]: '보',
  });

  #CommandTypes = Object.freeze({
    [this.#COMMAND_DELETE_CODE]: '삭제',
    [this.#COMMAND_ADD_CODE]: '추가',
  });

  constructor(n) {
    this.mapSize = n + 1;
    this.arr = Array.from(
      { length: this.mapSize },
      () => Array.from({ length: this.mapSize }, () => [false, false]) // pillar, floor(now -> right)
    );
  }

  checkBuild(x, y, buildType, commandType) {
    const commands = {
      [this.#CommandTypes[this.#COMMAND_DELETE_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]:
          this.checkDeletePillarPossible.bind(this, x, y),
        [this.#BuildTypes[this.#FLOOR_CODE]]:
          this.checkDeleteFloorPossible.bind(this, x, y),
      },
      [this.#CommandTypes[this.#COMMAND_ADD_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]: this.possibleAdd.bind(
          this,
          x,
          y,
          this.#PILLAR_CODE
        ),
        [this.#BuildTypes[this.#FLOOR_CODE]]: this.possibleAdd.bind(
          this,
          x,
          y,
          this.#FLOOR_CODE
        ),
      },
    };

    return commands[commandType][buildType]();
  }

  isValidPillar(x, y) {
    if (x < 0) return false;
    if (y < 0) return false;

    // 바닥에 설치할 경우
    if (y === 0) return true;

    // 한쪽 보 끝에 위치할 경우
    if (this.arr[x][y][1]) return true;
    if (x > 0 && this.arr[x - 1][y][1]) return true;

    // 다른 기둥 위에 있을 경우
    if (this.arr[x][y - 1][0]) return true;

    return false;
  }

  isValidFloor(x, y) {
    if (x < 0 || x >= this.mapSize - 1) return false;
    if (y <= 0) return false;

    // 한쪽 끝 부분이 기둥 위에 있는 경우
    if (this.arr[x][y - 1][this.#PILLAR_CODE]) return true;
    if (this.arr[x + 1][y - 1][this.#PILLAR_CODE]) return true;

    // 다른 보와 동시에 연결되어 있을 경우
    if (
      x &&
      this.arr[x - 1][y][this.#FLOOR_CODE] &&
      this.arr[x + 1][y][this.#FLOOR_CODE]
    )
      return true;

    return false;
  }

  possibleAdd(x, y, buildTypeCode) {
    if (this.arr[x][y][buildTypeCode]) return false;

    this.arr[x][y][buildTypeCode] = true;

    const result = buildTypeCode
      ? this.isValidFloor(x, y)
      : this.isValidPillar(x, y);

    this.arr[x][y][buildTypeCode] = false;

    return result;
  }

  delete(x, y, buildCode) {
    this.arr[x][y][buildCode] = false;
  }

  backupBeforeDelete(x, y, buildCode) {
    this.arr[x][y][buildCode] = true;
  }

  checkDeletePillarPossible(x, y) {
    if (!this.arr[x][y][this.#PILLAR_CODE]) return false;

    this.delete(x, y, this.#PILLAR_CODE);

    // pillar
    // 내 위에 기둥이 있을 경우.
    const overPillarStandPossible =
      y + 1 >= this.mapSize ||
      !this.arr[x][y + 1][this.#PILLAR_CODE] ||
      this.isValidPillar(x, y + 1);

    // 위쪽의 보가 없거나, 지탱할 만한 뭔가가 있어야 한다.
    const nowOverFloorStandPossible =
      y + 1 >= this.mapSize ||
      !this.arr[x][y + 1][1] ||
      this.isValidFloor(x, y + 1);

    // 왼쪽 보도 없거나, 버틸 수만 있다면 가능.
    const nowOverLeftFloorStandPossible =
      x - 1 < 0 ||
      y + 1 >= this.mapSize ||
      !this.arr[x - 1][y + 1][this.#FLOOR_CODE] ||
      this.isValidFloor(x - 1, y + 1);

    const result =
      overPillarStandPossible &&
      nowOverFloorStandPossible &&
      nowOverLeftFloorStandPossible;

    this.backupBeforeDelete(x, y, this.#PILLAR_CODE);

    return result;
  }

  checkDeleteFloorPossible(x, y) {
    if (!this.arr[x][y][1]) return false;

    this.delete(x, y, this.#FLOOR_CODE);

    // floor
    // 만약 현재 위치에 기둥이 있다면 유효한지 체크
    const isPillarStandPossible =
      !this.arr[x][y][this.#PILLAR_CODE] || this.isValidPillar(x, y);

    // 현재의 오른쪽에 세워진 기둥도 유효한지 체크.
    const isRightPillarStandPossible =
      x + 1 >= this.mapSize ||
      !this.arr[x + 1][y][this.#PILLAR_CODE] ||
      this.isValidPillar(x + 1, y);

    // 현재의 왼쪽 보도 유효한지 체크
    const isLeftFloorStandPossible =
      x - 1 < 0 ||
      !this.arr[x - 1][y][this.#FLOOR_CODE] ||
      this.isValidFloor(x - 1, y);

    // 현재의 오른쪽 보도 유효한지 체크
    const isRightFloorStandPossible =
      x + 1 >= this.mapSize ||
      !this.arr[x + 1][y][this.#FLOOR_CODE] ||
      this.isValidFloor(x + 1, y);

    const result =
      isPillarStandPossible &&
      isRightPillarStandPossible &&
      isLeftFloorStandPossible &&
      isRightFloorStandPossible;

    this.backupBeforeDelete(x, y, this.#FLOOR_CODE);

    return result;
  }

  updateBuildMap(x, y, buildCode, commandCode) {
    // 0 = delete => false, 1 = add => true
    this.arr[x][y][buildCode] = !!commandCode;
  }

  render(buildFrame) {
    buildFrame.forEach((command) => {
      const [x, y, buildCode, commandCode] = command;

      if (
        this.checkBuild(
          x,
          y,
          this.#BuildTypes[buildCode],
          this.#CommandTypes[commandCode]
        )
      ) {
        this.updateBuildMap(x, y, buildCode, commandCode);
      }
    });
  }

  getFinalBuildMaterials() {
    const buildMaterials = [];

    for (let i = 0; i < this.mapSize; i += 1) {
      for (let j = 0; j < this.mapSize; j += 1) {
        for (let buildCode = 0; buildCode < 2; buildCode += 1) {
          if (this.arr[i][j][buildCode]) {
            buildMaterials.push([i, j, buildCode]);
          }
        }
      }
    }

    return buildMaterials;
  }
}

const solution = (n, buildFrame) => {
  const buildMap = new BuildMap(n);
  buildMap.render(buildFrame);

  return buildMap.getFinalBuildMaterials();
};

결과

빠르게 통과하네요!

🔥 마치며

와... 진짜 힘들었네요.
그래도 이번에 클래스로 짜보면서, 객체를 통한 프로그래밍을 좀 더 이해하게 된 거 같아요.

특히 private class field 등 최근에 자바스크립트 스터디하면서 알게된 것들을 써보면서 코딩하는 게 재밌었어요!

아쉬운 점은 분명히 있습니다. 뭔가 쉽게 갈 수 있는 길을 돌아서 간 것 같아요
하지만 어찌되었던 간에, 스스로 결국 이겨냈다는 자부심이 너무 뿌듯해서, 제 알고리즘 레포에도 배운점과 반성한 점을 엄청 길게 썼네요. 🥰

그럼 다들, 도움이 되었길 바라며. 이상! 🌈

young_pallete

People are scared of falling to the bottom but born from there. What they've lost is nth. 😉