[Algorithm] 쿼드압축 후 개수 세기 ( Programmers / javascript )

문제 설명

0과 1로 이루어진 2^n * 2^n 크기의 2차원 정수 배열 arr 이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

 

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.

2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.

3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각혀 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

 

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로는 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 soultion 함수를 완성해주세요.

 

 

 

---

 

 

 

 

 

 

---

 

 

 

 

 

 

---

 

 

 

코드 풀이:

javascript

 

function solution(arr) {
  let zero = 0;
  let one = 0;
 
  function compress(x, y, size) {
    const pivot = arr[x][y];
    let same = true;
 
    for (let a = x; a < size + x; a++) {
      for (let b = y; b < size + y; b++) {
        if (pivot !== arr[a][b]) {
          same = false;
          break;
        }
      }
 
      if (!same) break;
    }
 
    if (same) {
      if (arr[x][y] === 1) one++;
      else zero++;
    } else {
      let dividends = size / 2;
 
      compress(x, y, dividends);
      compress(x, y + dividends, dividends);
      compress(x + dividends, y, dividends);
      compress(x + dividends, y + dividends, dividends);
    }
  }
 
  compress(0, 0, arr.length);
 
  return [zero, one];
}

 

 

위의 코드를 사용해서 예시 1번을 풀었을때 동작하는 방식을 시각화 한 작업이다.

 

solution([
  [1, 1, 0, 0],
  [1, 0, 0, 0],
  [1, 0, 0, 1],
  [1, 1, 1, 1],
])
 
 
 compress(0, 0, 4)
 ├── compress(0, 0, 2)
 │   ├── compress(0, 0, 1)  => one++
 │   ├── compress(0, 1, 1)  => one++
 │   ├── compress(1, 0, 1)  => one++
 │   └── compress(1, 1, 1)  => zero++
 ├── compress(0, 2, 2)      => zero++
 ├── compress(2, 0, 2)
 │   ├── compress(2, 0, 1)  => one++
 │   ├── compress(2, 1, 1)  => zero++
 │   ├── compress(3, 0, 1)  => one++
 │   └── compress(3, 1, 1)  => one++
 └── compress(2, 2, 2)
     ├── compress(2, 2, 1)  => zero++
     ├── compress(2, 3, 1)  => one++
     ├── compress(3, 2, 1)  => one++
     └── compress(3, 3, 1)  => one++

 

 

 

 

 

 

 

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

프로그래머스