[Level2] 쿼드압축 후 개수 세기

🛠 문제

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


👩🏻‍💻 해결 방법

영역의 맨 처음 값과 다른 값이 있으면 압축을 시도했다
x, y를 2로 나눈 길이만큼씩 압축하기 때문에 nn = n // 2를 구해주고 압축 후에 생기는 모든 영역을 재귀를 통해 각각 확인해주었다
압축이 된 영역에는 각각 숫자가 1개씩 존재하므로 answer[init] += 1을 통해 정답을 구할 수 있었다

소스 코드

def solution(arr):
    answer = [0, 0]
    n = len(arr)
    
    def comp(x, y, n):
        init = arr[x][y]
        for i in range(x, x + n):
            for j in range(y, y + n):
                if init != arr[i][j]:
                    nn = n // 2
                    comp(x, y, nn)
                    comp(x + nn, y, nn)
                    comp(x, y + nn, nn)
                    comp(x + nn, y + nn, nn)
                    return
        answer[init] += 1
        
    comp(0, 0, n)
    return answer

좋은 웹페이지 즐겨찾기