쿼드압축 후 개수 세기

 

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

프로그래머스

문제설명

분할 정복 문제이다.
초기 배열의 각 원소들을 카운트 한 다음 압축 결과에 따라 해당 키 값을 감소시키는 방법으로 풀이를 진행했다.

 

• 이차원 배열을 4 등분한 결과를 sub에 저장하여 새로운 배열을 만든다. 이때 각 배열은 이차원 배열을 슬라이스 한 결과를 반환하기 때문에 sub는 삼차원 배열이 된다.
• 새로 생성한 삼차원 배열을 반복하면서 요소들이 전부 같은 숫자로 이루어져 있는지 확인하고 해당 조건이 참이라면 cnt를 업데이트해 준다. 즉 요소의 모든 숫자가 같다면 해당 수 하나로 압축한다.
• 결과에 해당하지 않다면 함수를 재귀적으로 호출하여 결과를 얻는다.
• 만약 초기 배열의 모든 요소가 하나의 수밖에 존재하지 않는 경우도 예외 처리 해준다.

from collections import Counter


def solution(arr):
    cnt = Counter()
    for item in arr:
        cnt += Counter(item)

    if len(cnt) == 1:
        key, val = list(cnt.items())[0]
        cnt[key] -= val - 1
        return [cnt[0], cnt[1]]

    answer = dfs(cnt, arr)
    return [answer[0], answer[1]]


def dfs(cnt, arr):
    if len(arr) == 1:
        return cnt

    mid = len(arr) // 2
    sub = [
        [row[:mid] for row in arr[:mid]],
        [row[mid:] for row in arr[:mid]],
        [row[:mid] for row in arr[mid:]],
        [row[mid:] for row in arr[mid:]],
    ]

    for sub_arr in sub:
        if all(elem == 0 for row in sub_arr for elem in row):
            cnt[0] -= sum(row.count(0) for row in sub_arr) - 1
        elif all(elem == 1 for row in sub_arr for elem in row):
            cnt[1] -= sum(row.count(1) for row in sub_arr) - 1
        else:
            dfs(cnt, sub_arr)
    return cnt