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

문제주소 :programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

---

<문제 설명>

문제 설명

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

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

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

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

입출력 예

arr                                                                      result

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

 

<풀이법>

▒ 한줄 개념: numpy ▒ 

정사각형 배열에 대해서 4분할을 반복해나가는데, 해당 분할의 값이 0 또는 1로 통일될 때까지 분할하면 됩니다.

분할의 사이즈는 n*n에서 시작해서, 최소 1*1까지 될 것입니다.

 

2차원 배열을 가장 편하게 슬라이싱 하기 위해 numpy모듈을 사용했습니다.

 

• 전체 배열을 numpy 슬라이싱을 통해 4등분, 재귀 반복
• 배열 내 값의 합이 배열의 한 변의 제곱: 배열 내 값 모두 1 -> +1
• 배열 내 값의 합이 0: 배열 내 값 모두 0

 

<코드(Python)>

import numpy as np

def solution(arr):
    dic = {0:0, 1:0}
    arr = np.array(arr)
    dic = quad(np.array(arr), dic)
    return [dic[0],dic[1]]


def quad(arr, dic):
    if arr.sum() == len(arr)**2:
        dic[1] += 1
    elif arr.sum() == 0:
        dic[0] += 1
    else:
        dic = quad(arr[:len(arr) // 2, :len(arr) // 2], dic)
        dic = quad(arr[:len(arr) // 2, len(arr) // 2:], dic)
        dic = quad(arr[len(arr) // 2:, :len(arr) // 2], dic)
        dic = quad(arr[len(arr) // 2:, len(arr) // 2:], dic)

    return dic

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest