접근
우선 board에서 2x2를 만족하는 모든 것을 확인 후 삭제
사라진 공간을 채우고 다시 반복
이 과정을 삭제되는 것이 없을 때 까지 진행
전체 적인 흐름도는 위와 같았다.
그렇다면 여기서 board에서 2x2를 만족하는 모든 것을 어떻게 판별할 것인가.
어떤 행,열의 값과 주변 3개의 값이 같으면 2x2에 만족하게 된다. 하지만 2차원 배열에서 맨위 맨왼쪽부터 시작하게 된다면 해당 값의 오른쪽과 아래쪽 그리고 오른쪽 아래쪽을 비교하고 같으면 2x2에 만족하게 된다.
예를 들어 행열이 다음과 같이 있다고 했을 때
행열 [0][0]의 값은 a이고 [0][1]과 [1][0] 그리고 [1][1]이 모두 a이면 2x2행열에 만족한다. 하지만 바로 삭제하게 되면 board[0][1]에서 새로 비교를 할 수가 없다.
그리고 해당 값을 기준으로 오른쪽과 아래를 비교할 거기 때문에 행은 맨 아래쪽, 열은 맨 오른쪽을 for문으로 돌 필요가 없다.
다음으로 사라진 공간을 채우는 것은 어떻게 만들것인가.
맨 아래 행부터 시작하여 해당 행열의 값이 0이면 행을 위로 올리면서 가장 가까운 값을 가져오면 된다.
여기서 한 가지 짚고 넘어가야 할 것은 몇 번 삭제되었는지 구현할지다.
처음에는 map을 이용하여 0으로 치환할 값들의 행과 열을 map에 담고 map을 돌리면서 행과열에서 삭제하는 과정을 했지만 시간초과가 되었다.
간단하게 배열에 삭제 될 값의 주변 값까지 저장하는게 아니라 삭제될 값만 저장하고 board에서 해당 값과 주변 값까지 0으로 치환한다.
이후 삭제될 값이 없으면 board에서 0인 값들을 계산하여 리턴한다.
function solution(m, n, board) {
let answer = 0;
//String을 배열로 변환
board = board.reduce((acc,str)=>{
acc.push(str.split(''));
return acc;
},[]);
while(1){
//삭제 할 행열 저장할 공간
let arr = [];
//행과열을 순회하면서 삭제할 수 있는 2x2확인
// 단 해당 행과 열을 기준으로 오른쪽과 아래쪽을 확인하기 때문에 마지막 행과 마지막 열은 for문 순회에서 제외
for(let low=0; low<m-1; low++){
for(let col=0; col<n-1; col++){
let a = board[low][col], b = board[low][col+1];
let c = board[low+1][col], d = board[low+1][col+1];
//해당 값이 이미 삭제되었다면 다시 for문 순회
if(board[low][col] == 0) continue;
else if ( a == b && b == c && c == d ){
arr.push([low,col]);
}
}
}
if(arr.length == 0) {
//board 순회
answer = board.reduce((acc, a)=>{
// 해당 행에서 0인 값들의 갯수 acc에 저장
acc += a.filter(v=>!v).length;
return acc;
}, 0);
return answer;
}
// arr에서 반환하는 array의 값을 바로 전달받는다.
for(let [low, col] of arr){
board[low][col] = 0;
board[low][col+1] = 0;
board[low+1][col] = 0;
board[low+1][col+1] = 0;
}
// 맨 아래 행부터 돌면서 값 내리기
for(let low=m-1; low>0; low--){
// board의 해당 행이 모두 0이 없으면 for문 다시 진행
if(board[low].every(c => c!=0)) continue;
for(let col=0; col<n; col++){
for(let f=low-1; f>=0 && !board[low][col]; f--){
if(board[f][col] != 0) {
board[low][col] = board[f][col];
board[f][col] = 0;
break;
}
}
}
}
}
}
