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

문제 설명

0과 1로 이루어진 2^n x 2^n 크기의 2차원 정수 배열 arr이 주어집니다. 이 배열을 쿼드 트리와 같은 방식으로 압축하려 합니다.

압축 방식은 다음과 같습니다:

1. 특정 영역 S를 선택합니다.
2. S 내 모든 값이 같다면, 하나의 값으로 압축합니다.
3. 값이 다르면 S를 4개의 균일한 정사각형 영역으로 나누고, 각 영역에 대해 같은 방식으로 압축을 시도합니다.
4. 최종적으로 압축이 완료된 후, 배열에 남아있는 0의 개수와 1의 개수를 반환합니다.

---

제한 사항

• arr의 크기는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태입니다. (예: 1, 2, 4, 8, ..., 1024)
• arr는 정사각형 배열입니다.
• arr의 모든 요소는 0 또는 1입니다.

---

해결 방법

알고리즘: 분할 정복

1. 주어진 배열의 특정 영역 (sy, sx) ~ (ey, ex)가 모두 같은 값인지 확인합니다.
2. 만약 같은 값이라면 해당 숫자의 개수를 반환합니다.
3. 그렇지 않다면, 영역을 4개로 나누고 재귀적으로 같은 과정을 수행합니다.
4. 4개의 영역에서 반환된 결과를 합산하여 최종 결과를 구합니다.
5. 최적화 과정으로, 4개의 영역에서 동일한 결과(모두 1 또는 모두 0)라면 하나의 값으로 병합합니다.

---

시간 복잡도

• isUniform() 함수를 통해 특정 영역이 모두 동일한지 확인하는 데 최악의 경우 O(n^2) 시간이 소요됩니다.
• 배열을 4개로 나누는 과정이 반복되므로, 점화식은 T(n) = 4T(n/2) + O(n^2)로 표현됩니다.
• 마스터 정리에 의해 O(n^2)의 시간 복잡도를 가집니다.

---

구현 코드

function calc(a, b, c = 0) {
  return Math.floor((a + b) / 2) + c;
}

function getCount(sy, sx, ey, ex, arr) {        
  if(sy === ey && sx === ex) {
      return arr[sy - 1][sx - 1] === 1 ? [0, 1] : [1, 0];
  }    
  
  let midY = calc(sy, ey);
  let midX = calc(sx, ex);

  const counts = [
      getCount(sy, sx, midY, midX, arr),
      getCount(sy, midX + 1, midY, ex, arr),
      getCount(midY + 1, sx, ey, midX, arr),
      getCount(midY + 1, midX + 1, ey, ex, arr)
  ];
  
  let [zero, one] = counts.reduce(([z, o], [newZ, newO]) => [z + newZ, o + newO], [0, 0]);
  
  if(one === 4 && zero === 0) {
      return [0, 1];
  } else if(one === 0 && zero === 4) {
      return [1, 0];
  }
  
  return [zero, one];
}

function solution(arr) {
  return getCount(1, 1, arr.length, arr.length, arr);
}