[programmers] 기둥과 보 설치 (in JS)

문제

기둥과 보 설치 - 2020 kakao blind recruitment

Fact

• n이 주어졌을 때, 좌표는 [0, n+1]에 위치할 수 있으므로 좌표를 저장하는 2차원 배열의 크기는 (n+1) X (n+1)이다.
• 기둥 삭제 시
  • 기둥 위에 보는 [x, y+1], [x-1, y+1]에 설치되어있을 수 있다. 이 위치에 보가 설치되었다면, 기둥이 사라진 후에도 보가 위치할 수 있는지 확인해야 한다.
  • 기둥 위에 다른 기둥이 위치할 수 있다. [x, y+1]에 기둥이 설치되었다면, 기둥이 사라진 후에도 위에 있는 기둥이 위치할 수 있는지 확인해야 한다.
• 보 삭제 시
  • 삭제하고자 하는 보의 왼쪽 보(x-1, y)와 오른쪽 보(x+1,y)가 삭제된 벽에서도 위치할 수 있는지 확인해야 한다.
  • 보 위에 설치된 기둥은 [x, y], [x+1, y]에 위치할 수 있다. 이 위치에 기둥이 설치되었다면, 보가 사라진 후에도 위치할 수 있는지를 확인해야 한다.
• 주변 구조물이 어떠한 구조물이 삭제된 후에도 위치할 수 있는지 확인할 때, 그 주변 구조물이 설치가 되어있는 경우에만 확인하면 된다.

접근

• 각 배열에 보와 기둥이 설치되어있는지 여부를 저장하기 위해 {bo: boolean, pillar: boolean} 형태의 객체를 저장하였다.
• 보와 기둥이 설치되는 것으로 주어지는 x, y 좌표에만 불리안으로 설치 여부를 표시한다.
• 기둥과 보를 설치할 때는 주어진 조건 중 하나라도 만족한다면 해당 위치의 pillar나 bo를 true로 하였다.
• 기둥과 보를 삭제할 때는, 해당 구조물을 삭제함으로써 영향을 받을 수 있는 주변의 기둥과 보가 여전히 위치할 수 있는지 확인한다. 하나라도 위치할 수 없다면, 제거하지 않는다.
• 주변의 구조물을 확인할 때, 그 위치에 구조물이 설치되어있는 경우에만 확인하다.

복잡도

• 공간 복잡도 : O(k * k) where k >= 5 && k <= 100
  • 벽면의 크기가 주어졌을 때, (k+1) * (k+1) 크기의 배열에 좌표의 상태를 저장해야 한다.
• 시간 복잡도 : O(N)
  • build_frame을 한 번 순회하여 값을 구할 수 있다.

알게된 점

• 자바스크립트에서 fill로 배열이나 객체를 넘겨주면, instance가 아닌 Reference를 넘겨준다. 그러므로 각각의 instance를 넘겨주고 싶다면, fill().map()으로 각 요소를 변형시켜야 한다.

처음 wall 변수를 초기화할 때, 자바스크립트의 fill로 객체를 담은 array로 채워주었다.
문제는 wall의 배열들이 같은 배열의 reference였다는 것이다.

  const wall = new Array(n + 1).fill(
  new Array(n + 1).fill({ pillar: 0, bo: 0 }));

이 문제를 해결하기 위해 fill()로 임의의 값을 넣어준 후, map()을 돌면서 각 요소들을 변형시켜주었다.

  const wall = new Array(n + 1)
    .fill()
    .map((_) => new Array(n + 1).fill().map((_) => ({ pillar: 0, bo: 0 })));

• javascript에서 배열과 객체를 다른 변수에 할당하면 레퍼런스 참조로 복사하게 된다.
• spread로 복사하게 된다면, shallow copy가 된다. 상위의 프로퍼티 중 기본 자료형만 새로운 메모리에 할당되고, 그 외에는 original의 메모리 주소를 참조하게 된다.

  const a = [1, { hi: "hi" }];
  const b = [...a];
  console.log(b); //[ 1, { hi: 'hi' } ]
  b[0] = 100;
  b[1].hi = "bye";
  console.log(a); // [ 1, { hi: 'bye' } ]
  console.log(b); // [ 100, { hi: 'bye' } ]

코드

const PILLAR = 0;
const BO = 1;
const REMOVE = 0;
const INSTALL = 1;

const getInitialWall = (n) => {
  const wall = new Array(n + 1)
    .fill()
    .map((_) =>
      new Array(n + 1).fill().map((_) => ({ pillar: false, bo: false }))
    );
  return wall;
};

const isValidPillar = (wall, x, y) => {
  const isOnFloor = y === 0;
  const isOnBo = wall[y][x].bo || (x - 1 >= 0 && wall[y][x - 1].bo);
  const isOnPillar = y - 1 >= 0 && wall[y - 1][x].pillar;
  return isOnFloor || isOnBo || isOnPillar;
};

const isValidBo = (n) => (wall, x, y) => {
  const checkOneSideOnPillar =
    y - 1 >= 0 &&
    (wall[y - 1][x].pillar || (x + 1 <= n && wall[y - 1][x + 1].pillar));
  const checkBothOnBo =
    x - 1 >= 0 && wall[y][x - 1].bo && x + 1 < n && wall[y][x + 1].bo;
  return checkOneSideOnPillar || checkBothOnBo;
};

const toggleStatusOfWall = (wall, x, y, type) => {
  wall[y][x][type] = !wall[y][x][type];
};

const checkNoEffect = (validFunc, testWall, locList, n, type) => {
  const passAllValidFunc = locList
    .filter((loc) => loc.x >= 0 && loc.y <= n && testWall[loc.y][loc.x][type])
    .every((loc) => validFunc(testWall, loc.x, loc.y));
  return passAllValidFunc;
};

const removeBoIfPossible = (wall, x, y, n) => {
  const boLoc = [
    { x: x - 1, y },
    { x: x + 1, y },
  ];
  const pillarLoc = [
    { x, y },
    { x: x + 1, y },
  ];
  toggleStatusOfWall(wall, x, y, "bo");

  const noEffectOnBo = checkNoEffect(isValidBo(n), wall, boLoc, n, "bo");
  const noEffectOnPillar = checkNoEffect(
    isValidPillar,
    wall,
    pillarLoc,
    n,
    "pillar"
  );
  if (noEffectOnBo && noEffectOnPillar) {
    return;
  }
  toggleStatusOfWall(wall, x, y, "bo");
};

const removePillarIfPossible = (wall, x, y, n) => {
  const boLoc = [
    { x, y: y + 1 },
    { x: x - 1, y: y + 1 },
  ];
  const pillarLoc = [{ x, y: y + 1 }];
  toggleStatusOfWall(wall, x, y, "pillar");

  const noEffectOnBo = checkNoEffect(isValidBo(n), wall, boLoc, n, "bo");
  const noEffectOnPillar = checkNoEffect(
    isValidPillar,
    wall,
    pillarLoc,
    n,
    "pillar"
  );

  if (noEffectOnBo && noEffectOnPillar) {
    return;
  }
  toggleStatusOfWall(wall, x, y, "pillar");
};
const installIfPossible = (validFunc, wall, x, y, type) => {
  if (!validFunc(wall, x, y)) {
    return;
  }
  wall[y][x][type] = true;
};

const getFinalFrame = (wall, n) => {
  const finalFrame = [];
  for (let x = 0; x <= n; x++) {
    for (let y = 0; y <= n; y++) {
      if (wall[y][x].pillar) {
        finalFrame.push([x, y, PILLAR]);
      }
      if (wall[y][x].bo) {
        finalFrame.push([x, y, BO]);
      }
    }
  }
  return finalFrame;
};

function solution(n, build_frame) {
  const wall = getInitialWall(n);

  for (const [x, y, type, action] of build_frame) {
    if (type === PILLAR) {
      if (action === INSTALL) {
        installIfPossible(isValidPillar, wall, x, y, "pillar");
      } else {
        removePillarIfPossible(wall, x, y, n);
      }
    } else {
      // BO
      if (action === INSTALL) {
        installIfPossible(isValidBo(n), wall, x, y, "bo");
      } else {
        removeBoIfPossible(wall, x, y, n);
      }
    }
  }
  const finalFrame = getFinalFrame(wall, n);
  return finalFrame;
}

소감...

원래 소감은 안썼지만 이 문제는 소감을 써야겠다...
이 문제는 나한테 얕은 복사와 깊은 복사를 몰랐던 나를 아주 크게 혼내주었다.
초반에 초기화할 때, '='연산자로 할당한 배열의 요소들은 original 배열의 메모리를 참조하고 있었다. 따라서 배열에서 한 요소의 값만 바꿔도 전체 배열의 모든 값들이 변경되는 것처럼 보였다.

두 번째 위기는 배열이 깊은 복사가 된다고 생각해서 문제가 생겼다. 알고리즘 풀면서 javascript 이해가 부족했던 점을 채울 수 있어서 다행인 것 같다.