[programmers] 프렌즈 4블록 (in JS)

문제

프렌즈 4블록-2018 KAKAO BLIND RECRUITMENT

Fact

• 2x2형태로 모두 같은 모양인지 확인 할 때, row의 index는 m-1보다 작아야 하고, column의 index는 n-1보다 작아야 한다.
• 2X2 형태로 모두 같은 모양인지 확인할 때, 알파벳인 경우에만 모두 같은지를 확인해야 한다.

접근

• 보드에서 2X2로 배치된 블락이 없을 때까지 다음을 반복한다.
  - r은 [0, m-1)범위를, c는 [0, n-1]범위를 반복한다.
  - 같은 모양인지를 체크하는 보드와 같은 크기의 2차원 배열을 만들고, 값을 false로 채운다. -> checkBoard
  - 해당 위치의 보드가 알파벳인 경우, 오른쪽, 아래쪽, 오른쪽 대각선 아래가 모두 같은 모양인지 확인한다.
  - 같은 모양일 경우, checkBoard에서 해당되는 네 곳을 true로 변경한다.
  - 보드에 대한 순회가 끝난 뒤, checkBoard에서 체크된 것이 몇 개인지 확인한다.
  - 체크된 갯수를 전체 체크된 갯수에 더한다.
  - 체크된 것이 없을 경우, 반복문을 빠져나온다.
  - 체크된 부분을 보드에서 없애고, 위에 있는 블락들을 밑으로 내려보낸다.
  - checkBoard를 위에서 아래로, 왼쪽에서 오른쪽으로 순회하며, 그 부분의 보드가 체크되었는지 확인한다.
  - 체크되었다면, 그 위치부터 올라가며 위에 있는 보드를 아래로 내려보낸다.
  - 맨 위의 (r=0)의 블락은 EMPTY로 채운다.
• 전체 체크된 갯수를 반환한다.

복잡도

• 공간 복잡도 : O(M * N)
  - 높이 m, 폭 n 크기의 2차원 배열이 필요하다.
• 시간 복잡도 : O(M * N)
  

알게된 점

• 배열안의 값이 문자열일 경우, 인덱스로 접근하여 수정할 수 없다.
  -> 배열 안의 문자열을 다 배열로 바꾸어서, 인덱스로 접근하여 바로 수정할 수 있도록 하였다.

const board = stringBoard.map((str) => Array.from(str));

• crash되었음을 체크할 때는 다른 2차원 배열에 체크해야 한다. 그래야, 기존 배열에 영향을 주지않고, 전체 보드에서 어떠한 부분이 crash되는지 확인할 수 있다.

코드

const EMPTY = ".";
const dir = [
  [0, 0],
  [1, 0],
  [0, 1],
  [1, 1],
];
const checkCrash = (r, c, crashBoard) => {
  dir.forEach(([dr, dc]) => (crashBoard[r + dr][c + dc] = true));
};

const countCrash = (checkBoard) => {
  const nCrash = checkBoard
    .flat()
    .reduce((count, check) => (check ? count + 1 : count), 0);
  return nCrash;
};

const fillEmptySpace = (board, checkBoard, m, n) => {
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (!checkBoard[r][c]) {
        continue;
      }
      for (let i = r; i > 0; i--) {
        board[i][c] = board[i - 1][c];
      }
      board[0][c] = EMPTY;
    }
  }
};
const getCheckBoard = (m, n) =>
  new Array(m).fill().map((_) => new Array(n).fill(false));

const isAllSame = (board, r, c) => {
  const block = board[r][c];
  return dir.every(([dr, dc]) => block === board[r + dr][c + dc]);
};
function solution(m, n, stringBoard) {
  const board = stringBoard.map((str) => Array.from(str));
  let totalCrash = 0;
  while (true) {
    const checkBoard = getCheckBoard(m, n);
    for (let r = 0; r < m - 1; r++) {
      for (let c = 0; c < n - 1; c++) {
        if (board[r][c] === EMPTY || !isAllSame(board, r, c)) {
          continue;
        }
        checkCrash(r, c, checkBoard);
      }
    }
    const count = countCrash(checkBoard);
    if (count === 0) {
      break;
    }
    totalCrash += count;
    fillEmptySpace(board, checkBoard, m, n);
  }

  return totalCrash;
}