[Programmers/파이썬] 프로그래머스(Lv.2) 쿼드압축 후 개수 세기 문제풀이

문제 설명

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

프로그래머스

 

 

사고 흐름

1. 배열을 쪼개면서 압축이 가능한지 확인한다 -> 분할 정복

2. 어떻게 배열을 4등분하지? -> n은 2로 나누고, 좌표를 이용하자 !

 

문제 핵심과 알고리즘

분할 정복 + 압축 가능 여부 확인 + 4등분하기 

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

 

압축이 가능하면 (start와 다 동일하면) answer 하나 증가

압축이 불가능하면 (start와 다르면) 해당 배열을 4등분해서 다시 압축 여부를 확인한다. 

 

문제 풀면서 헤맸던 부분

딱히 없었다. 

 

총평

예전같았으면 지레 겁먹었을 문제였는데 지금은 바로 풀었다. 핵심은 배열을 4등분하는 것 이였다. 이때 빠르게 좌표를 이용한 등분을 생각해서 빨리 풀 수 있었다.