[프로그래머스] 퀴드압축 후 개수 세기

문제

프로그래머스 월간 코드 챌린지 시즌 1 퀴드압축 후 개수 세기

programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

언어

자바스크립트(JavaScript)

 

접근 방법

1. 재귀 함수를 작성하고 실행한다.
2. 배열을 0 또는 1로 압축이되는지 확인하고, 압축이 되면 결과에 추가한다.
3. 만약 압축이 되지 않는다면 4등분한다.
4. 4등분 한 배열로 재귀 함수를 실행한다.

코드

function solution(arr) {
    const answer = [0, 0];
    compress(arr, answer)
    return answer;
}

const compress = (arr, answer) => {
    const compressResult = checkCompress(arr)
    if (compressResult === 0){
        answer[0] ++;
    }else if (compressResult === 1){
        answer[1] ++;
    }else{
        const {arr1, arr2, arr3, arr4} = divideArr(arr);
        compress(arr1, answer);
        compress(arr2, answer);
        compress(arr3, answer);
        compress(arr4, answer);
    }
}

const divideArr = (arr) => {
    const n = arr.length/2;
    const arr1 = new Array(n).fill(-1).map(e=>new Array(n).fill(-1));
    const arr2 = new Array(n).fill(-1).map(e=>new Array(n).fill(-1));
    const arr3 = new Array(n).fill(-1).map(e=>new Array(n).fill(-1));
    const arr4 = new Array(n).fill(-1).map(e=>new Array(n).fill(-1));
    for (let y=0; y<2*n; y++){
        for (let x=0; x<2*n; x++){
            if (x<n && y<n){
                arr1[y][x] = arr[y][x];
            }else if (x>=n && y<n){
                arr2[y][x-n] = arr[y][x];
            }else if (x<n && y>=n){
                arr3[y-n][x] = arr[y][x];
            }else if (x>=n && y>=n){
                arr4[y-n][x-n] = arr[y][x];
            }
        }
    }
    return {arr1, arr2, arr3, arr4}
}

// 1로 압축이 가능하면 1 리턴
// 0으로 압축이 가능하면 0 리턴
// 압축이 불가능하면 -1 리턴
const checkCompress = (arr) => {
    let isAllZero = true;
    let isAllOne = true;
    arr.forEach(e1=>{
        e1.forEach(e2=>{
            if (e2===0){
                isAllOne = false;
            }
            if (e2===1){
                isAllZero = false;
            }
        })
    })
    if(isAllZero){
        return 0;
    }else if (isAllOne){
        return 1;
    }else{
        return -1;
    }
}

복기

1. 미리 생각하고 풀면 어렵지 않다.
2. 2차원 배열 초기화할 때 new Array(n).fill(0).map(e=>new Array(n).fill(0))로 해야한다. new Array(n).fill(new Array(n))로 하면 안된다.