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

문제 설명

프로그래머스 레벨 2의 문제로 월간 코드 챌린지 시즌 1 에 출제된 문제입니다.

쿼드압축 방식을 통해 데이터를 압축 후 해당 배열에 0과 1의 데이터의 개수를 반환합니다.

 

위 그림을 통해 쉽게 이해할 수 있습니다. 영역의 숫자가 모두 같지 않다면 4가지 영역으로 분리한 후 다시 영역의 모든 숫자가 같은지 확인합니다.

 

위 방식을 반복하다 모든 영역의 숫자가 같다면 그 영역을 병합 하고 마지막엔 전체 영역의 0과 1의 각각의 개수를 반환합니다.

 

풀이

def split_arr(arr):
    arr_1 = []
    arr_2 = []
    arr_3 = []
    arr_4 = []
    size = len(arr) // 2

    for i in range(0, size):
        row = []
        for j in range(0, size):
            row.append(arr[i][j])

        arr_1.append(row)

    for i in range(size, len(arr)):
        row = []
        for j in range(0, size):
            row.append(arr[i][j])

        arr_2.append(row)

    for i in range(0, size):
        row = []
        for j in range(size, len(arr)):
            row.append(arr[i][j])

        arr_3.append(row)

    for i in range(size, len(arr)):
        row = []
        for j in range(size, len(arr)):
            row.append(arr[i][j])

        arr_4.append(row)

    return arr_1, arr_2, arr_3, arr_4


def fun(arr, result):
    common_element = arr[0][0]

    is_all_same = True
    for row in arr:
        for element in row:
            if element != common_element:
                is_all_same = False
                break

        if not is_all_same:
            break

    if is_all_same:
        result.append(common_element)
        return

    arr_1, arr_2, arr_3, arr_4 = split_arr(arr)

    fun(arr_1, result)
    fun(arr_2, result)
    fun(arr_3, result)
    fun(arr_4, result)


def solution(arr):
    result = []
    fun(arr, result)

    return [result.count(0), result.count(1)]

 

변수, 함수 설명

split_arr(arr): 배열을 4개의 영역으로 구분후 반환하는 함수입니다.

fun(arr, result): arr이 모두 같은 요소로 이루어졌을 경우 result에 해당 요소를 추가한 후 종료하는 재귀함수입니다.

 

간단 설명

이 문제는 재귀함수를 사용하여 해결했습니다.

 

split_arr 함수는 이차원배열을 4가지 배열(영역)으로 나누어 반환하는 역할을 합니다. 

 

fun에 들어올 경우 해당 배열이 모두 같은 요소로 이루어졌는지 확인합니다. 만약 모두 같은 요소라면 result에 요소를 추가하고 종료합니다.

 

아닐 경우 해당 영역을 4개의 영역으로 나누어 재귀적으로 함수를 호출합니다. 결국 가로 1, 세로 1의 하나의 요소만이 남게된다면 같은 요소로 이루어졌기 때문에 result에 추가 되며 종료됩니다.