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

👉 쿼드압축 후 개수 세기

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 입니다.

👉 입출력 예

👉 입출력 예에 대한 설명

✍ 내 코드

---

def quadtree_last_check(arr):
    """ 길이가 2인 사각형의 값 """
    one = sum(arr[0]) + sum(arr[1])
    zero = 4 - one
    if one == 4:
        return (0, 1)
    elif zero == 4:
        return (1, 0)
    else:
        return (zero, one)


def spliting_arr(side_len, arr):
    if side_len == 2:
        return quadtree_last_check(arr)

    target = [[0, 0], [0, side_len // 2], [side_len // 2, 0], [side_len // 2, side_len // 2]]
    check = ()
    result = [0, 0]
    zero_cnt, one_cnt = 0, 0

    for i in range(4):  # 4등분
        split_arr = [[0] * (side_len // 2) for _ in range(side_len // 2)]

        for j in range(0, side_len // 2):  # x 증가
            for q in range(0, side_len // 2):  # y 증가
                split_arr[j][q] = arr[target[i][0] + j][target[i][1] + q]

        one = sum(sum(split_arr, []))
        zero = (side_len // 2) ** 2 - one
        if zero == 0:  # zero가 0이니까 모두 1
            one_cnt += 1
            check = (0, 1)
        elif one == 0:  # one이 0이니까 모두 0
            zero_cnt += 1
            check = (1, 0)
        else:
            check = spliting_arr(side_len // 2, split_arr)  # 안합쳐지면 재귀

        result[0] += check[0]
        result[1] += check[1]

        # 4등분 한 모든 결과가 0, 1일경우 예외처리
        if zero_cnt == 4:
            result = [1, 0]
        elif one_cnt == 4:
            result = [0, 1]

    return tuple(result)


def solution(arr):
    side_len = len(arr[0])
    if side_len == 1:
        if arr[0][0] == 1:
            return [0, 1]
        else:
            return [1, 0]
    else:
        answer = list(spliting_arr(side_len, arr))
    return answer

---

✍ 팁

파이썬의 numpy를 이용하면 훨씬 간단하게 풀 수 있지만 numpy는 일부러 쓰지 않았다.
(numpy는 다차원 배열을 처리하기 위한 패키지이다 / 외부 라이브러리이기 때문에 코테에서는 사용 못 하는 곳이 더 많다)

팁이라면은 해당 사각형을 길이에 따라서 분기점을 나누고 재귀를 이용하면 나름 간단히 풀 수 있다.
나중에 numpy를 이용해서도 다시 한번 풀어볼 문제