[JS][프로그래머스 -LEVEL 2 -쿼드압축 후 개수 세기 ]

문제

말그대로 원래의 길이 /2 압축하면서 네모 상자에 같은수가 존재하는 경우에는 압축을 한다는 것이다.

DFS 로 풀어야되는데 바보같이 BFS 로 풀어서 코드가 많이 지저분하다.. BFS 로 왜 풀었는지 모르겠다. return 으로 이제 신경안쓰는 부분입니다. 이렇게 적으면 금방 풀리는 문제였다.

문제 풀이 방식

• 0.0 을 기준으로 [0.0] ,[0,4],[4,0] ,[4,4] 이런식으로간다.
• 이때 더 가야되는지 아닌지 확인하는 함수가 필요
• 똑같은 수 일때는 더이상안가도 되니까 분할을 하지않는다.

코드

function solution(arr) {
    var answer = [];
    var queue_answer=[[[0,0],arr.length]  ];
   var zer_o=0;
    var zer_1=0;

    const check_for= function(y,x,count){
         var main_here= arr[y][x];
         var chekcc=-1;
        for(var here_y=y; here_y<y+count; here_y++){
            for(var here_x=x; here_x<x+count; here_x++){
                if(arr[here_y][here_x]!=main_here){
                    chekcc=0;
                    break;
                }
            }
        }
        if(chekcc==-1){
                for(var here_y=y; here_y<y+count; here_y++){
                 for(var here_x=x; here_x<x+count; here_x++){
                 arr[here_y][here_x]=null;
              
            }
        }
            if( main_here!=null){
                //answer.push(main_here); 
                if(main_here==1){
                    zer_1+=1;
                }
                if(main_here==0){
                    zer_o+=1;
                }
            }
             
        }
        return chekcc
    }
    
    const four_for= function(y,x,count){
       
       var change_y= [0,+count,0,+count];
       var change_x=[0,0,+count,+count];
        
        for(var i=0; i<4; i++){
            
            if(y+change_y[i] <arr.length && x+change_x[i] <arr[0].length && 
               isNaN( arr[ y+change_y[i] ][ x+change_x[i] ])==false && count>1
              ){
              queue_answer.push([[y+change_y[i], x+change_x[i]],count])   
            }
        }
    }
   
  
     while(queue_answer.length>0){
       var [[y1,x1],ccount]= queue_answer.shift();
        
      
        var he= check_for(y1,x1,ccount);
         
         if(ccount>1 && he!=-1){
              four_for(y1,x1,ccount/2); 
         }
       
        
     }

   
    for(var fianl_y=0; fianl_y<arr.length; fianl_y++){
        for(var final_x=0; final_x<arr[0].length; final_x++){
            if(arr[fianl_y][final_x]==1){
                zer_1+=1;
            }
            if(arr[fianl_y][final_x]==0){
                zer_o+=1;
            }
        }
    }
    return [zer_o,zer_1]

}

남의 풀이

function solution(arr, answer = [0, 0]) {
  if (arr.length === 1) { //네모 한칸일 경우
    answer[arr[0]] += 1;
    return
  } else if (check(arr) >= 0) {//check 됐을경우(압축가능)
    answer[check(arr)] += 1; //check가 0,1을 리턴하기 때문에 맞는 인덱스에 1더해준다.
    return
  } else {
    for (let i = 0; i < 2; i++) {
      for (let j = 0; j < 2; j++) {
        //2중 for문을 이용해 4칸으로 나눠서 체크한다.
        solution(parseArr(arr, i, j), answer);
      }
    }
  }
  return answer;
}
//배열이 압축이 되는지 체크
//배열의 전체합과 칸의 수 비교를 통해서 판단했다.
function check(arr) {
  let cnt = 0;
  for (const x of arr) {
    cnt += x.reduce((acc, cur) => acc + cur, 0);
  }
  if (cnt === arr.length ** 2) return 1;  //1로 압축
  else if (cnt === 0) return 0; //0으로 압축
  else return -1; //아닐경우
}
//범위에 맞는 배열 parsing하기
//배열의 길이와 i,j(위의 for문에서의 i,j이다.)를 이용해서 배열 파싱
function parseArr(arr, i, j) {
  const len = arr.length / 2;
  arr = arr.slice(i * len, i * len + len);
  arr = arr.map((v) => v.slice(j * len, j * len + len));
  return arr;
}