[python] 프로그래머스 - 쿼드압축 후 개수 세기 (월간 코드 챌린지 시즌1)

🤔문제 해결

압축문제 백준에서도 비슷한 문제를 풀어본적이 있다. 

리스트를 실제로 자르지 말고 나뉘는 인덱스만 구해서 해결하는게 좋다.

인덱스를 구할 때는 네모의 시작점의 위치만 구한다. 거기에 + 네모의 길이만큼 해주면 네모를 완성시킴

시작점을 기준으로 하면 위의 경우는 0, 0 그리고 크기는 8이다.

다음 4가지는

• 0, 0, 4
• 0, 4, 4
• 4, 0, 4
• 4, 4, 4

다음 네모는 크기를 절반으로 나누고 x에 더하거나 y에 더하거나 x와 y 둘다 더해서 시작값을 만든다.

 

다음은 이 네모가 모두 같은 숫자인지 판별하는 것인데

네모중 하나의 값을 초기값으로 잡고 네모안의 값을 하나씩 비교해가면서 초기값과 다른게 하나라도 있으면 압축할 수 없으므로 또 그 네모를 잘라준다!

 

💻소스 코드

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 arr[i][j] != init:  # 한번이라도 다르면 그 네모는 압축불가
                    nn = n // 2
                    comp(x, y, nn)
                    comp(x, y + nn, nn)
                    comp(x + nn, y, nn)
                    comp(x + nn, y + nn, nn)
                    return

        # 무사히 다 통과했다면 압축가능
        answer[init] += 1

    comp(0, 0, N)
    return answer

 

📕문제 확인

출처: 프로그래머스

링크: https://programmers.co.kr/learn/courses/30/lessons/68936?language=python3

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