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

문제

쿼드압축 후 개수 세기

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

 

 

풀이

설명

쿼드압축을 진행 후, 최종적으로 남는 0의 개수와 1의 개수를 구하는 문제입니다.

 

압축은 다음과 같이 진행됩니다.

1. 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

 

3번 과정은 재귀 방식을 통해 값을 반환받아 더하는 방식으로 구현할 수 있습니다.

 

예시 코드

function solution(arr) {
  return compress(0, 0, arr.length);

  function compress(x, y, size) {
    const initial = arr[x][y];
    let isSame = true;

    for (let i = x; i < x + size; i++) {
      for (let j = y; j < y + size; j++) {
        if (arr[i][j] === initial) continue;

        isSame = false;
        break;
      }

      if (!isSame) break;
    }

    if (isSame) return initial === 0 ? [1, 0] : [0, 1]; // [0의 개수, 1의 개수]
    else {
      const halfSize = size / 2;
      const topLeft = compress(x, y, halfSize);
      const topRight = compress(x, y + halfSize, halfSize);
      const bottomLeft = compress(x + halfSize, y, halfSize);
      const bottomRight = compress(x + halfSize, y + halfSize, halfSize);

      return [
        topLeft[0] + topRight[0] + bottomLeft[0] + bottomRight[0],
        topLeft[1] + topRight[1] + bottomLeft[1] + bottomRight[1],
      ];
    }
  }
}