68936: 쿼드압축 후 개수 세기

Link : programmers.co.kr/learn/courses/30/lessons/68936

---

1. 문제

• 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
  1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
  2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
  3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
  arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

 

---

2. 문제의 조건

• arr의 행, 열의 개수는 1이상 1024 이하이며 2^n 형태를 하고 있다.
• arr은 정사각형 배열이다.
• arr은 0또는 1로만 이루어져있다.

 

---

3. 문제 접근

• 아이디어
  
  해당 방식은 쪼개면서 접근하는 방식으로 "재귀"를 이용하여 풀 수 있겠다고 생각하였습니다.
  만약 쪼개진 형태가 모두 0또는 1로 이루어져 있다면, 0개수를 증가, 1개수를 증가를 하면 되고, 만약 다른 데이터가 존재한다면 4분면으로 나누고 재귀를 도시면됩니다.

 

---

4. 풀이 방법

• [x개수, y개수]를 띄운 리스트를 작성합니다.
• 해당 형태가 전부 0또는 1으로만 이루어져있는지 확인하고
  만약 0으로만 이루어져있다면, [1, 0] 을 반환하고 1로만 이루어져있다면 [0, 1]을 반환합니다.
• 만약 0또는 1이 섞여있다면, 4분면으로 쪼개 재귀를 탐색을 하고 현재 값에 더해줍니다.
  (list의 덧셈은 별도로 구현을 해줘야합니다.)
• result를 리턴합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/156

 

---

 

cjw.git@gmail.com