[프로그래머스] Lv2 - 쿼드압축 후 개수 세기 (파이썬)

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

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

 

def solution(arr):
    N = len(arr)
    answer = [0, 0]

    def press(start, end, N):
        temp = arr[start][end]
        for i in range(start, start+N):
            for j in range(end, end+N):
                if temp != arr[i][j]:
                    N //= 2
                    press(start, end, N)
                    press(start, end+N, N)
                    press(start+N, end, N)
                    press(start+N, end+N, N)
                    return
        answer[temp] += 1

    press(0, 0, N)
    return answer

 

풀이
1. N을 2로 나누어 가면서 네 가지 영역을 재귀 함수로 똑같이 반복해준다.
2. 전부 같을 경우 해당 값을 1 증가

 

복잡해 보이지만 단순하다.

재귀 함수가 관건