[프로그래머스] 쿼드 압축 후 개수 세기 (javascript)

728x90
반응형

주어진 범위 내에서 하나라도 다른 수가 있으면 시작위치를 기준으로 길이/2 만큼 y,x에 더해서

새로운 시작위치를 만들고 새로운 길이를 len/2로 해서 재귀함수로 던져준다.

 

중간에 주어진 범위에서 모든 수가 같다면 해당 수의 개수를 +1 더해주고 더 길게 들어가지 않고

len이 1이 되면 더이상 쪼갤 수 없으므로 해당 수를 +1더해주고 끝낸다.

 

--- new 풀이!

function solution(arr) {
    var answer = [0,0];
    let n=arr.length;
    
   go(0,0,n);
    
    function go(y,x,len){
        let cur=arr[y][x];
        let pass=true;
        for(let i=y;i<y+len;i++){
            for(let j=x;j<x+len;j++){
                if(arr[i][j]!=cur){
                    pass=false;
                    let half=parseInt(len/2);
                    go(y,x,half);
                    go(y+half,x,half);
                    go(y,x+half,half);
                    go(y+half,x+half,half);
                    break;
                }
            }
            if(!pass)break;
        }
        
       if(pass){
           answer[arr[y][x]]+=1;
       } 
        
    }
    
    
    return answer;
}

 

 

---

 

function solution(arr) {
    var answer = [0,0];
    const xpos=[1,0,1];
    const ypos=[0,1,1];// 시작 지점 기준
    function check(y,x,len,cur){
        for(let i=y;i<y+len;i+=1){
            for(let j=x;j<x+len;j+=1){
                if(cur!=arr[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
    
    function compress(y,x,len){
        if(len==1){
            answer[arr[y][x]]+=1;
            return;
        }
        let cur=arr[y][x];
        

        if(!check(y,x,len,cur)){//압축하기
            for(let i=y;i<y+len;i+=len/2){
                for(let j=x;j<x+len;j+=len/2){
                    compress(i,j,len/2);
                }
            }
        }else{
            answer[cur]+=1;
        }
    }
    let len=arr.length;
    if(!check(0,0,len,arr[0][0])){
        for(let i=0;i<len;i+=len/2){
            for(let j=0;j<len;j+=len/2){
                compress(i,j,len/2);
            }
        }
    }else{
        answer[arr[0][0]]+=1;
    }
    
    return answer;
}
728x90
반응형
TAGS.

Comments