쿼드압축 후 개수 세기

쿼드압축 후 개수 세기
월간 코드 챌린지 시즌1 
1701명 완료

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

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

풀고 나서 다른 분들의 코드를 보니 재귀를 사용한 간략한 풀이들이 너무 많았다..
부끄럽긴 하지만..

def solution(array):
    width = len(array)
    while width > 1:
        for x in range(len(array) // width):
            for y in range(len(array) // width):
                all_0, all_1 = check(array, x * width, y * width, width)
                if all_0:
                    fill(array, x * width, y * width, width, 0)
                elif all_1:
                    fill(array, x * width, y * width, width, 1)
        width //= 2
    return list(count(array))


def count(array):
    count_0, count_1 = 0, 0
    for x in range(len(array)):
        for y in range(len(array)):
            if array[x][y] == 0:
                count_0 += 1
            elif array[x][y] == 1:
                count_1 += 1
    return count_0, count_1


def fill(array, x, y, width, num):
    for i in range(x, x + width):
        for j in range(y, y + width):
            array[i][j] = 2
    array[x][y] = num


def check(array, x, y, width):
    all_0, all_1 = True, True
    for i in range(x, x + width):
        for j in range(y, y + width):
            if array[i][j] == 0:
                all_1 = False
            elif array[i][j] == 1:
                all_0 = False
            else:
                return False, False
    return all_0, all_1

테스트 1 〉	통과 (1.35ms, 10.3MB)
테스트 2 〉	통과 (1.34ms, 10.3MB)
테스트 3 〉	통과 (1.06ms, 10.3MB)
테스트 4 〉	통과 (0.32ms, 10.3MB)
테스트 5 〉	통과 (320.13ms, 12.2MB)
테스트 6 〉	통과 (203.68ms, 12.2MB)
테스트 7 〉	통과 (182.55ms, 12.3MB)
테스트 8 〉	통과 (160.86ms, 12.2MB)
테스트 9 〉	통과 (132.27ms, 12.3MB)
테스트 10 〉	통과 (459.57ms, 19MB)
테스트 11 〉	통과 (0.24ms, 10.3MB)
테스트 12 〉	통과 (0.28ms, 10.2MB)
테스트 13 〉	통과 (130.78ms, 12.3MB)
테스트 14 〉	통과 (739.16ms, 18.9MB)
테스트 15 〉	통과 (876.29ms, 18.9MB)
테스트 16 〉	통과 (326.12ms, 12.3MB)

속도는 느려지겠지만
코드를 좀 더 정리하면

def solution(array):
    width = len(array)
    nums_0, nums_1 = 0, 0
    while width >= 1:
        for x in range(len(array) // width):
            for y in range(len(array) // width):
                all_0, all_1 = check(array, x * width, y * width, width)
                if all_0:
                    nums_0 += 1
                    fill(array, x * width, y * width, width)
                elif all_1:
                    nums_1 += 1
                    fill(array, x * width, y * width, width)
        width //= 2
    return [nums_0, nums_1]


def fill(array, x, y, width):
    for i in range(x, x + width):
        for j in range(y, y + width):
            array[i][j] = 2


def check(array, x, y, width):
    all_0, all_1 = True, True
    for i in range(x, x + width):
        for j in range(y, y + width):
            if array[i][j] == 0:
                all_1 = False
            elif array[i][j] == 1:
                all_0 = False
            else:
                return False, False
    return all_0, all_1

테스트 1 〉	통과 (2.21ms, 10.3MB)
테스트 2 〉	통과 (2.02ms, 10.2MB)
테스트 3 〉	통과 (1.75ms, 10.3MB)
테스트 4 〉	통과 (0.54ms, 10.3MB)
테스트 5 〉	통과 (595.50ms, 12.2MB)
테스트 6 〉	통과 (378.44ms, 12.2MB)
테스트 7 〉	통과 (325.81ms, 12.2MB)
테스트 8 〉	통과 (295.03ms, 12.1MB)
테스트 9 〉	통과 (265.36ms, 12.2MB)
테스트 10 〉	통과 (1007.86ms, 18.9MB)
테스트 11 〉	통과 (0.54ms, 10.3MB)
테스트 12 〉	통과 (0.52ms, 10.4MB)
테스트 13 〉	통과 (265.33ms, 12.2MB)
테스트 14 〉	통과 (1246.97ms, 19MB)
테스트 15 〉	통과 (1380.66ms, 18.8MB)
테스트 16 〉	통과 (470.10ms, 12.3MB)