[1차] 프렌즈4블록

[1차] 프렌즈4블록

2020.08.02

const rotateMatrix = (matrix) => {
  const rowLength = matrix.length;
  const colLength = matrix[0].length;
  const newMatrix = [];
  for (let i = 0; i < colLength; i++) {
    const temp = [];
    for (let j = rowLength - 1; j >= 0; j--) {
      temp.push(matrix[j][i]);
    }
    newMatrix.push(temp);
  }
  return newMatrix;
};

const shouldExplode = (matrix, row, col) => {
  const current = matrix[row][col];
  const right = matrix[row][col + 1];
  const under = matrix[row + 1][col];
  const rightUnder = matrix[row + 1][col + 1];
  return current == right && current == under && current == rightUnder;
};

const enroll = (row, col, hash) => {
  if (!hash.hasOwnProperty(row)) {
    hash[row] = [[col, col + 1]];
  } else {
    const lastEl = hash[row][hash[row].length - 1];
    const previousStart = lastEl[0];
    const previousEnd = lastEl[1];
    if (previousEnd + 1 < col) {
      hash[row].push([col, col + 1]);
    } else {
      lastEl[0] = Math.min(previousStart, col);
      lastEl[1] = Math.max(previousEnd, col + 1);
    }
  }
};

const explode = (matrix, hash = {}, count = 0) => {
  const rowLength = matrix.length;
  const colLength = matrix[0].length;
  for (let i = 0; i < colLength - 1; i++) {
    for (let j = 0; j < rowLength - 1; j++) {
      if (shouldExplode(matrix, j, i)) {
        enroll(j, i, hash);
        enroll(j + 1, i, hash);
      }
    }
  }
  if (Object.keys(hash).length == 0) {
    return count;
  }
  for (const index in hash) {
    const spliceList = hash[index];
    while (spliceList.length) {
      const [start, end] = spliceList.pop();
      const length = end + 1 - start;
      matrix[index].splice(start, length);
      count += length;
      for (let i = 0; i < length; i++) {
        matrix[index].push(NaN);
      }
    }
  }
  return explode(matrix, {}, count);
};

const solution = (m, n, board) => {
  const rotated = rotateMatrix(board);
  return explode(rotated);
};

• 이걸 실전에서 어떻게 푸냐...

• 터지고 내려온 다음 빈 자리를 NaN으로 채웠는데 이는 터지는 4개를 검사할 때 NaN == NaN이 false가 나온다는 점을 이용하여 빈 자리(NaN으로 채워진 자리)는 다시 터트리지 않기 위함이다.
  (일종의 버그를 활용한 건데 괜찮은건가)

• 숫자를 채우고(ex:0) shouldEnroll에서 type검사를 하는 방법도 있는데 뭐가 더 나은지는 모르겠다.

• 한참 헤맨 이유 중 하나가 터질 요소들을 검사할 때 (회전한) 행렬을 기준으로 열이 아닌 행을 먼저 검사해서였다.

• 회전한 행렬을 기준으로 오른쪽에서 왼쪽으로 터져서 자리를 채울 것을 생각하면 왼쪽에서 시작하든 오른쪽에서 시작하든 열을 기준으로 검사해야 꼬이지 않는다.

• 이 문제는 다들 헤매지 않았나 싶다. 다른 사람의 풀이를 보니 코드 길이가 어마어마...