圧縮後数世紀

質問する

質問:https://programmers.co.kr/learn/courses/30/lessons/68936

配列を圧縮し、0と1を配列に戻す問題を上図に示します.

解決策

再び復帰して解決した.最大の配列を入力して4等分してチェックする必要があるため,再帰を利用することができる.
終了するたびに、パラメータの答え(配列)が更新されます.
配列は参照であるため再帰を終了し,初期関数として出現しても更新後の配列値は変わらない.

は終了条件(2つのif文)

を返す.

arr(パラメータ)の長さが1の場合は1マスとなり、終了します.

arrはcheck(圧縮可能かどうか)によって終了する.

非再帰的終了条件(else)
2のfor文を使用してarrを4格子に分けて比較します.for文の範囲変数i,jを用いてparseArr(arr,i,j)で処理した.

解答の過程.
答えは[0個の数、1個の数]からなる.すなわち、以下に示すように、値をインデックスとして使用することができる.
-arr長さが1の場合はanswer[arr[0]] += 1-検査が有効な場合はanswer[check(arr)] += 1

check-圧縮性チェック

与えられた配列の整数と解を用いた.

合計==長さ*長さ(全格数)の場合は1

を返します.

合計=0は0

を返します.

else return -1

true、falseではなく1、0、-1を返します.
答えは[0個の数、1個の数]からなる.answer[check(arr)] += 1のように
インデックスをcheck関数の戻り値として指定し、加算のために1、0、および-1を返します.

ParseArr-タイル4等分

2のfor文からi,j値をパラメータとして取得する.
i row/jをcolumnとして想像し、配列を変換する.len:指定されたアレイの長さの半分
len変数を使用してsliceを使用してrowを切り取り、columnも切り取ります.

code

変数名、パラメータ名が友好的ではないため、多くの注釈が残されている.

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;
}

の最後の部分

問題のデザインを見るのに少し時間がかかりました.正直、私は自分の考えでコードを書いたが、意外にも一気に通過した.
一度復帰を利用して解決し、通過したときの気持ちの良い問題です.
今はまだ鬼才を制御するのは容易ではない.