圧縮後数世紀

問題の説明

2 nx 2 nの大きさの2次元整数配列arrがあり,0と1からなる.このarrを四叉木と同じように圧縮したいです.具体的な方法は以下の通りです.

圧縮する特定の領域をSとして定義します.

Sのすべての数字が同じ値である場合、Sは1つの数字に圧縮される.

でない場合は、Sを4つの均一な正方形領域に正確に配置します(I/O例を参照).これを分割し、正方形領域ごとに同じ圧縮を試みます.

arrはパラメータです.上記のようにarrを圧縮する場合は、解関数を完了し、配列の最終的な残りの0と1の数を配列に入れて返します.

せいげんじょうけん

arrの行数は1または1024以下であり、2の繰返し平方数である.つまりarrの行数は1、2、4、8…、1024のうちの1つ.

arrの各行の長さはarrの行数に等しい.すなわちarrは正方形アレイである.

arrの各行のすべての値は0または1です.

I/O例

arrresult[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]][4,9][[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]][10,15]

I/O例説明

I/O例#1

の下図は、所与のarrを圧縮するプロセスを示す.

最終圧縮結果には4つの0,9つの1があるため、[4,9]を返さなければならない.

I/O例#2

の下図は、所与のarrを圧縮するプロセスを示す.

最終圧縮結果には10個の0,15個の1があるため、[10,15]を返さなければならない.

に答える

function solution(arr) {
  // 정사각형이 1*1이 될 때까지 나눠야 하는 횟수
  let count = Math.log2(arr.length);

  // 정사각형의 한 변의 길이 n
  let n = arr.length;

  let answer = [0, 0];
  
  for(let i=0; i<=count; i++) {
    let tempArr = [];
    for(let j=0; j<arr.length; j+=n) {
      for(let k=0; k<arr[0].length; k+=n) {
	// n번째 내부 배열과 내부 배열의 n번째 요소까지 잘라서 정사각형꼴로 만든다
        let square = arr.slice(j, j+n).map(e => e.slice(k, k+n));
	// 정사각형 안의 모든 값을 더한다.
        let sum = square.flatMap(e => e).reduce((a, b) => a+b);
	// 더한 값이 0이면 모든 요소가 0이고, n*n이면 모든 요소가 1이고, 둘 다 아니면 tempArr에 푸시한다.
        if(sum === 0) answer[0]++
        else if(sum === n*n) answer[1]++
        else tempArr.push(square);
      }
    }
    // tempArr에 푸시한 2차원 배열을 1차원 배열로 arr에 갱신
    arr = tempArr.flatMap(e => e);
    // 정사각형의 한 변의 길이를 반으로 줄이고, n이 1이 될 때까지 반복
    n /= 2;
  }
  return answer;
}