1. 문제 설명

• 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
  1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
  2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
  3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
• arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

2. 제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

3. 입출력 예제

let output = solution([[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]);
console.log(output); // [4,9]

output = solution([[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]);
console.log(output); // [10,15]	

4. 입출력 예 설명

5. 문제 풀이

(1) 풀이 1

function solution(arr) {

    const comp = (rowS, rowE, colS, colE, arr) => {
        if (rowS === rowE) {
            if (arr[rowS][colS]) return [0, 1];
            return [1, 0];
        };
        
        let rowM = parseInt((rowS + rowE) / 2);
        let colM = parseInt((colS + colE) / 2);
        
        const leftU = comp(rowS, rowM, colS, colM, arr);
        const rightU = comp(rowS, rowM, colM + 1, colE, arr);
        const leftD = comp(rowM + 1, rowE, colS, colM, arr);
        const rightD = comp(rowM + 1, rowE, colM + 1, colE, arr);

        let zero = leftU[0] + rightU[0] + leftD[0] + rightD[0];
        let one = leftU[1] + rightU[1] + leftD[1] + rightD[1];

        if (zero === 4 && one === 0) return [1, one];
        else if (zero === 0 && one === 4) return [zero, 1];
        else return [zero, one];
    };
    
    return comp(0, arr.length - 1, 0, arr.length - 1, arr);
};

(2) 풀이 2

function solution(arr) {
    let len = arr.length / 2;
    
    if (len < 1) {
        if (arr[0][0]) return [0, 1];
        return [1, 0];
    }
    
    const leftUp = arr.slice(0, len).map(el => el.slice(0, len));
    const rightUp = arr.slice(0, len).map(el => el.slice(len));
    const leftDown = arr.slice(len).map(el => el.slice(0, len));
    const rightDown = arr.slice(len).map(el => el.slice(len));
    
    const leftU = solution(leftUp);
    const rightU = solution(rightUp);
    const leftD = solution(leftDown);
    const rightD = solution(rightDown);
    
    let zero = leftU[0] + rightU[0] + leftD[0] + rightD[0];
    let one = leftU[1] + rightU[1] + leftD[1] + rightD[1];
    
    if (zero === 4 && one === 0) return [1, one];
    else if (zero === 0 && one === 4) return [zero, 1];
    else return [zero, one];
};

6. 문제 풀이 해설