[JS] 프렌즈4블록

 

 

난이도: Lv. 2

정답률: 56%

문제: https://school.programmers.co.kr/learn/courses/30/lessons/17679

프로그래머스

 

 

알고리즘

1. 블록이 지워진 후 위에 있는 블록을 내릴 때 열 방향으로 처리하는 것보다 행 방향으로 처리하는 것이 더 간단하다. 따라서 원본 board의 전치행렬을 생성한다.

2. 1.에서 생성한 전치행렬을 순회하며 4블록을 확인한다. 4블록임이 확인되면 삭제할 인덱스를 "행번호,열번호" 형태로 Set에 추가한다. 굳이 Set을 안 써도 될 것 같긴 하다. 하지만 4블록임이 확인되자마자 그 블록들을 없애서는 안 된다.

3. 2.에서 생성된 Set에 있는 블록들을 공백으로 대체한다. 이때 공백으로 대체되는 문자의 개수를 정답에 더해준다.

4. 블록을 내린다.

5. 2~4 과정을 반복하며 Set의 크기가 0인 경우 더 이상 지울 블록이 없음을 의미하므로 정답을 리턴한다.

 

 

코드

function solution(m, n, board) {
    let answer = 0;

    // 전치행렬 생성
    let boardCopy = Array.from({ length: n }, () => { return Array.from({ length: m }, () => 0) });
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            boardCopy[n - 1 - j][i] = board[i][j];
        }
    }

    while (true) {
        const deleteIdxSet = new Set();

        // 4블록이면 삭제할 인덱스 집합에 추가
        for (let row = 0; row < n - 1; row++) {
            for (let col = 0; col < m - 1; col++) {
                if (boardCopy[row][col] !== ' ' && boardCopy[row][col] === boardCopy[row][col + 1] &&
                    boardCopy[row][col] === boardCopy[row + 1][col] && boardCopy[row][col] === boardCopy[row + 1][col + 1]) {
                    deleteIdxSet.add(row + "," + col);
                    deleteIdxSet.add((row + 1) + "," + col);
                    deleteIdxSet.add(row + "," + (col + 1));
                    deleteIdxSet.add((row + 1) + "," + (col + 1));

                }
            }
        }

        // 삭제
        const deleteIdxArr = Array.from(deleteIdxSet);
        answer += deleteIdxArr.length;
        for (let idx of deleteIdxArr) {
            const numIdx = idx.split(',');
            boardCopy[numIdx[0]][numIdx[1]] = ' ';
        }

        // 블록 내리기
        for (let row = 0; row < n; row++) {
            boardCopy[row] = boardCopy[row].filter((value) => value !== ' ');
            const zeroPadding = m - boardCopy[row].length;
            for (let i = 0; i < zeroPadding; i++) { boardCopy[row].unshift(' '); }
        }

        if (!deleteIdxSet.size) { return answer; }
    }
}

 

 

주저리

처음에 열 방향으로 블록 내리려고 했는데 아무리 생각해 봐도 코드 짜는 게 굉장히 귀찮을 것 같다는 생각이 들어서 행 방향으로 블록을 내리기로 했다. 근데 블록은 제대로 없애는데 정답은 이상해서 왜 그런지 확인해 봤는데 Set에 중복된 배열이 담겨있었다. 위에 풀이에서는 "행번호,열번호"로 Set에 담았는데 처음에는 [행번호, 열번호] 배열로 Set에 담았더니 중복된 배열이 들어가 있었다. 배열 내부 원소들이 일치하는지 보는 게 아니라 배열의 참조값으로 일치 여부를 보기 때문에 그런 것 같아서 고쳤더니 정답도 잘 나왔다.