Portfolio

문제

풀이

은찬


function solution(arr) {
    const answer = [0, 0];
    const m = arr.length;
    
    const check = (sx, sy, length) => {
        const first = arr[sx][sy];
        const half = Math.floor(length / 2);
        
        for(let i = sx; i < sx + length; i++){
            for(let j = sy; j < sy + length; j++){
                if(arr[i][j] !== first){
                    check(sx, sy, half);
                    check(sx + half, sy, half);
                    check(sx, sy + half, half);
                    check(sx + half, sy + half, half);
                    
                    return;
                }
            }
        }
        
        answer[first]++;
    }
    
    check(0, 0, m);
    
    return answer;
}

재영


const getNextXYs = (startX, startY, endX, endY) => {
  const halfX = parseInt((endX + startX) / 2);
  const halfY = parseInt((endY + startY) / 2);

  return {
    1: {
      startX: halfX,
      startY,
      endX,
      endY: halfY,
    },
    2: {
      startX,
      startY,
      endX: halfX,
      endY: halfY,
    },
    3: {
      startX,
      startY: halfY,
      endX: halfX,
      endY,
    },
    4: {
      startX: halfX,
      startY: halfY,
      endX,
      endY,
    },
  };
};

const check = (arr, startX, startY, endX, endY, checkValue) => {
  for (let i = startX; i < endX; i += 1) {
    for (let j = startY; j < endY; j += 1) {
      if (arr[i][j] !== checkValue) return false;
    }
  }

  return true;
};

const dfs = (arr, length, startX, startY, endX, endY, counts) => {
  if (arr.length === length) {
    const checkValue = arr[startX][startY];

    if (check(arr, startX, startY, endX, endY, checkValue)) {
      counts[checkValue] += 1;
      return;
    }
  }

  if (length === 1) {
    counts[arr[startX][startY]] += 1;
    return;
  }

  // NOTE: 사분면을 맞춰주기 위해 0은 true로 설정.
  const compressed = [true, false, false, false, false];
  const nextXYs = getNextXYs(startX, startY, endX, endY);

  compressed.forEach((isCompress, idx) => {
    if (!idx) return;

    const { startX: sX, startY: sY, endX: eX, endY: eY } = nextXYs[idx];
    isCompress = check(arr, sX, sY, eX, eY, arr[sX][sY]);

    if (isCompress) {
      counts[arr[sX][sY]] += 1;
      return;
    }

    dfs(arr, parseInt(arr.length / 2), sX, sY, eX, eY, counts);
  });
};

const solution = (arr) => {
  let counts = { 0: 0, 1: 0 };
  dfs(arr, arr.length, 0, 0, arr.length, arr[0].length, counts);

  return Object.values(counts);
};

효성

참고한 풀이입니다!


function solution(arr) {
    let total = [0, 0];
    
    const compress = (arr, n) => {
        
        const cur = arr[0][0];
        
        if(n <= 1) {
            total[cur] += 1;
            return;
        }
        
        const sum = arr.reduce((sum, row) => sum + row.reduce((a, b) => a + b), 0);
        
        if(sum === 0 || sum === n * n) {
            total[cur] += 1;
            return;
        }
        
        const divide1 = arr.slice(0, n/2);
        const divide2 = arr.slice(n/2);
        
        compress(divide1.map(value => value.slice(0, n/2)), n/2);
        compress(divide1.map(value => value.slice(n/2)), n/2);
        compress(divide2.map(value => value.slice(0, n/2)), n/2);
        compress(divide2.map(value => value.slice(n/2)), n/2);
    }
    
    compress(arr, arr.length);
    
    return total;
}

쿼드 압축 후 개수 세기

문제

풀이