[Python] 프로그래머스 쿼드압축 후 개수 세기 풀이

문제 확인

프로그래머스

 

나의 풀이

실제로 재귀 함수 느낌이 나는 그런 그림이 주어진다

쿼드 압축은 매 시행 마다 압축이 가능한 지 확인하고, 불가능하다면 4개의 동일한 부분을 나눠서 다시 확인한다. 압축 시도 → 분할 후 압축 재 시도의 과정이 반복되기 때문에 재귀 함수를 활용할 수 있다.

• 압축의 형태를 비교하는 과정에서, 2차원 리스트 슬라이싱이 필요했다.
• 리스트를 2차원 슬라이싱 하려면, 다음과 같이 리스트 컴프리헨션을 사용하면된다.
  • [row[j : j + n // 2] for row in arr[i : i + n // 2]]

# (0의 개수, 1의 개수)
# 재귀? -> 길이가 2일 때 까지 반복 실행
# 압축된 경우 -> 개수 먼저 세기 / 나머지 -> 마지막에 한 번에
cnt = [0, 0]

def get_units(n):
    zeros = [[0 for _ in range(n)] for _ in range(n)]
    ones = [[1 for _ in range(n)] for _ in range(n)]
    return zeros, ones

def quad_zip(arr, n):
    global cnt
    # 바로 구성할 수 있는 경우
    zeros, ones = get_units(n)
    if arr == zeros:
        cnt[0] += 1
        return
    elif arr == ones:
        cnt[1] += 1
        return
    # 더 이상 쪼갤 수 없는 경우
    if n == 2:
        for nums in arr:
            for num in nums:
                if num == 0: cnt[0] += 1
                else: cnt[1] += 1
        return
    # 쪼갤 수 있는 경우
    zeros, ones = get_units(n // 2)
    # 압축 가능한 지 확인
    for i in range(0, n, n // 2):
        for j in range(0, n, n // 2):
            quad = [row[j : j + n // 2] for row in arr[i : i + n // 2]]
            if quad == zeros:
                cnt[0] += 1
            elif quad == ones:
                cnt[1] += 1
            else: quad_zip(quad, len(quad))
    return

def solution(arr):
    quad_zip(arr, len(arr))
    return cnt

 

다른 사람 풀이

매 시행마다 첫 원소를 지정하고, 다른 원소가 나올 경우 4 등분을 진행한다.

이 경우 조건문을 최소화할 수 있어 더 좋은 풀이라고 생각한다.

def solution(arr):
    answer = [0, 0]
    n = len(arr)
    
    def quard(x, y, n):
        first = arr[x][y]
        
        for i in range(x, x + n):
            for j in range(y, y + n):
                if arr[i][j] != first:
                # 4 분할
                    n //= 2
                    quard(x, y, n) # 왼쪽 위
                    quard(x, y + n, n) # 오른쪽 위
                    quard(x + n, y, n) # 왼쪽 아래
                    quard(x + n, y + n, n) # 오른쪽 아래
                    return
        # 전부 통과한 경우 압축
        answer[first] += 1
    
    quard(0, 0, n)
        
    return (answer)

[프로그래머스] 쿼드압축 후 개수 세기 - python