[CodeKata] 프로그래머스 : 3.25(목), 프렌즈4블록

🥋 Ooooth!! (Level 2)

테트리스와 유사하되, 2x2 블록만 깨지는 패턴이다.

주의해야 할 점은, 중첩되는 부분이 있을 수 있으므로 모든 깨지는 경우를 확인한 뒤 전체적으로 지워줘야 한다.

 

 🧮 풀이

function solution(m, n, board) {
  board = board.map(block => block.split(""))

  while (true) {
    let newBoard = JSON.parse(JSON.stringify(board))
    let breakPoint = [];
    for (let x = 0 ; x < m-1 ; x++) {
      for (let y = 0 ; y < n-1 ; y++) {
        if (board[x][y] === board[x][y+1] && board [x+1][y] === board[x+1][y+1] && board [x][y] === board[x+1][y+1]) {
      breakPoint.push([x,y]);
    }
  }
}

  while (breakPoint.length) {
    const now = breakPoint.shift();
    const nowX = now[0];
    const nowY = now[1];
    newBoard[nowX][nowY] = newBoard[nowX+1][nowY] = newBoard[nowX][nowY+1] = newBoard[nowX+1][nowY+1] = undefined;
  }
    
  for (let y = 0 ; y < n ; y++) {
    const newCol = Array.from({ length: m }, (_, i) => newBoard[i][y]).filter(e => e);

    for (let x = m-1 ; x >= 0 ; x--) {
      newBoard[x][y] = newCol.pop();
    }
  }

  if (JSON.stringify(board) === JSON.stringify(newBoard)) break;
    board = newBoard
  }
  return board.flat().filter(block => !block).length
}

1. while 반복문 순회, breakPoint 확인

• 먼저, board 각 요소를 문자열이 아닌 각 글자의 2차원 배열로 map() + split() 해준다.
• while 반복문을 순회하며, 종료조건은 board와 newBoard(2x2 깨진 후의 board) 가 같은 경우이다. (변화가 없음)
• newBoard는 board를 복사한 뒤, 블록 제거작업을 진행한다. 의존성을 없애기 위한 깊은복사(JSON 메서드) 를 적용한다.
• 우선, board를 이중순회하며 2x2가 같은 좌표를 찾는다. +1 인덱스와 비교하므로, m,n까지가 아닌 m-1, n-1까지만 탐색하면 됨.
• (0,0) === (0,1), (1,0) === (1,1), (0,0) === (1,0) 이 같다면, 자동적으로 (0,1) === (1,1) 도 같아지는 조건이다.
• 위 조건의 (x,y)는 2x2 블록의 좌상단 좌표이다. 이를, breakPoint에 push() 한다.

2. newBoard 2x2 블록 제거작업

• 다음으로, 축적된 breakPoint 들을 활용해 newBoard에서 2x2 블록 제거작업을 진행한다.
• 인덱스를 하나씩 shift() 한 뒤, newBoard에서 해당 인덱스의 2x2를 undefined 로 대치하며 제거한다.

3. newBoard 재정렬 작업

• 블록 제거작업이 끝난 뒤, 중간에 비어있는 블록들을 위에 블록을 내려주는 재정렬 작업을 진행한다.
• y(열)을 순회하며 newCol 배열을 만들어준다. 이는, newBoard의 각 열에서 undefined를 filter() 로 제외한 배열이다.
• 이를 x(행)을 순회하며 newBoard에 쌓아준다. 이 때, 행을 역으로 순회하는것이 밑에서부터 쌓기 유리하다.

4. 반복문 종료 및 결과값 반환

• 만약, board와 newBoard가 같다면 더 이상의 2x2 블록제거 동작이 없다는 의미이다. 이 땐, break를 해준다.
• 위 조건에 맞지 않다면, board를 현재의 newBoard로 최신화한 뒤, 반복문을 다시 적용한다.
• board를 flat() 하여 1차원 배열로 변환한다. 여기서, undefined가 제거된 블록이므로 이 갯수만큼 반환한다.

 

🖇 리뷰

모범답안과 흐름은 비슷하나, 좀 더 심플하게 풀 수 있는 방법이 있었다.

function solution(m, n, board) {
    board = board.map(v => v.split(''));

    while (true) {
        let founded = [];

        // 찾기
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                if (board[i][j] && board[i][j] === board[i][j - 1] && board[i][j] === board[i - 1][j - 1] && board[i][j] === board[i - 1][j]) {
                    founded.push([i, j]);
                }
            }
        }

        if (! founded.length) return [].concat(...board).filter(v => ! v).length;

        // 부수기
        founded.forEach(a => {
            board[a[0]][a[1]] = 0;
            board[a[0]][a[1] - 1] = 0;
            board[a[0] - 1][a[1] - 1] = 0;
            board[a[0] - 1][a[1]] = 0;
        });

        // 재정렬
        for (let i = m - 1; i > 0; i--) {
            if (! board[i].some(v => ! v)) continue;

            for (let j = 0; j < n; j++) {
                for (let k = i - 1; k >= 0 && ! board[i][j]; k--) {
                    if (board[k][j]) {
                        board[i][j] = board[k][j];
                        board[k][j] = 0;
                        break;
                    }
                }
            }
        }
    }
}

1. founded는 breakPoint와 같은 역할의 배열이다. 이것이 존재하지 않는다면, 종료조건이므로 이 때 board에서 0의 길이를 반환
2. 2x2 블록을 부수는 동작을 founded의 forEach()로 진행했다. 또한, 0 역시 undefined와 유사하게 취급되므로 이를 적용한 모습
3. 재정렬은 행은 역순(m-1 -> 0), 열은 정순(0 -> n-1)로 순환한다. 해당 행에, 0이 있을경우 위쪽과 치환이 필요하므로 continue
4. 각 열에서, 다시 k를 통해 현재 행(i)보다 위쪽에서 0이 아닌 값을 찾는다. 이 board[k][j]를 board[i][j]와 치환하는 것이다.