알고리즘 코드카타 105 - 쿼드압축 후 개수 세기

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

프로그래머스

문제 설명
0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한사항
arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

 

예시1)

0이 4개 1이 9개이므로 [4, 9]를 return

 

 

예시2)

0이 10개 1이 15개이므로 [10, 15]를 return

 

주어진 2차원 배열을 쿼드 압축해서 0과 1의 갯수를 세려는 알고리즘, 배열을 활용해야하기 때문에 numpy라이브러리를 사용해보기로 했다. 배운지 좀 오래돼었기 때문에 리마인드하는 느낌으로 검색을 적극적으로 사용했다.

 

import numpy as np

def solution(arr):
    arr = np.array(arr)

 

주어진 리스트를 넘파이를 사용해서 배열로 바꿔주었다. 이제 이 배열을 압축하는 과정을 만들어보자.

 

def is_uniform(array):
    return np.all(array == array[0, 0])

 

먼저 배열의 모든 요소가 동일한지 검증하는 함수를 작성한다. 동일할 경우, True를 반환한다.

 

def solution(arr):
    arr = np.array(arr)
    
    if is_uniform(arr):
        return arr[0, 0]
    else:

 

작성해둔 is_uniform(array)를 사용해서 배열을 압축한다. 즉, 배열의 모든 요소가 같을 경우 하나의 요소를 반환한다. 이번에는 else부분으로 이동해서 모든 요소가 같지 않을 경우, 배열을 분리하는 과정을 작성해보자.

 

if is_uniform(arr):
        return arr[0, 0]
    else:
        l = arr.shape[0] // 2

 

shape를 사용해서 arr배열의 차원의 크기를 구해준다. arr는 정사각 행렬이므로 (n, n)형태를 가질테니 행, 열 어떤 것을 지정해도 상관 없다. 그리고 그것을 2로 분할해준다. 배열의 길이는 항상 2의 배수인 정수기 때문에 처음에는 몫을 구하는 //가 아니라 단순 나눗셈인 /를 사용했다. 하지만 결과값이 int가 아니라 float였기때문에 //로 수정을 해주었다.

 

if is_uniform(arr):
        return arr[0, 0]
    else:
        l = arr.shape[0] // 2
        top_left = arr[:l, :l]
        top_right = arr[l:, :l]
        lower_left = arr[:l, l:]
        lower_right = arr[l:, l:]
        print(top_left)

 

l을 기준으로 배열을 4부분으로 분할한다. numpy를 사용하면서 가장 놀란 부분인데 확실히 배열을 다루는 것은 numpy를 쓰는 것이 이해하기도 쉽고 방법도 간단했다.

 

def quadtree(array):
    
    if is_uniform(array):
        return array[0, 0]
    else:
        l = array.shape[0] // 2
        top_left = array[:l, :l]
        top_right = array[l:, :l]
        lower_left = array[:l, l:]
        lower_right = array[l:, l:]
        
        return [
            quadtree(top_left),
            quadtree(top_right),
            quadtree(lower_left),
            quadtree(lower_right)
        ]

 

재귀함수를 적용하기 위해서 기존에 작성하던 solution함수를 quadtree함수로 수정해주었다. 해당함수를 재귀적으로 작동해서 쿼드압축을 반복적으로 수행한다. 설명하자면, top_left로 분할된 부분에 다시 quadtree함수를 거치게 되어 분할된 부분의 모든 원소가 같을경우 is_uniform함수를 통해서 압축이 된다. 이제 쿼드압축은 완료됐으며 1과 0의 갯수만 세서 출력하면 된다.

 

가장 어려운 부분은 지났다고 생각했는데 quadtree함수를 거쳐서 받은 리턴값이 리스트안에 list와 int가 섞여있는 상태라서 그 상태로 데이터를 판단하기 복잡했다. 리스트를 평탄화하고 전체길이(1의 갯수 + 0의 갯수)에서 평탄화한 리스트의 합(1의 갯수)를 빼주면 0의 갯수와 1의 갯수를 모두 구할 수 있을 것이다.

 

def flatten_list(lst):
    result = []
    for i in lst:
        if isinstance(i, list):
            result.extend(flatten_list(i))
        else:
            result.append(i)
    return result

 

넘파이를 활용해서 평탄화까지 진행하려고 했지만 에러가 발생해서 결국 사용을 하지 못했다... 대신 새로 함수를 작성해서 적용해주기로했다. 문제하나 푸는데 함수를 4개나 작성하는건 좀 과한것같기는 하지만...

 

def solution(arr):
    arr = np.array(arr)
    quadtree_arr = quadtree(arr)
    quadtree_arr = flatten_list(quadtree_arr)

    return print(quadtree_arr)

 

위에서 작성한 평탄화 함수를 활용해서 쿼드압축된 배열을 1차원 배열로 바꿔주었다. 이제 정말정말 마지막 단계만 남았다.

 

def solution(arr):
    arr = np.array(arr)
    quadtree_arr = quadtree(arr)
    quadtree_arr = flatten_list(quadtree_arr)
    
    len_arr = len(quadtree_arr)
    arr_in_one = sum(quadtree_arr)
    
    answer = [len_arr - arr_in_one, arr_in_one]

    return answer

 

이 함수로 테스트 케이스를 모두 통과했고 채점에 들어갔다.

??????

 

질문 답변을 찾아보니 해당 케이스의 에러는 arr의 모든 원소가 같은 숫자일때 발생한다고 한다. 결국 예외처리를 해줘야한다는건데... 함수를 여러개 사용한터라 에러가 발생하는 부분을 검증하는 것이 쉽지않았다.

 

그래서 vscode로 넘어가서 에러가 발생하는 위치를 하나씩 찾아보았다.

 

for i in lst:
        if isinstance(i, list):
            result.extend(flatten_list(i))
        else:
            result.append(int(i))
    return result

 

에러가 발생한 위치는 flatten_list함수의 해당부분이었다. flatten_list함수는 np.list를 인자로 받는데 모든 값이 같을 경우 np.int값이 flatten_list함수에 입력되어서 에러가 발생하는 것이었다.

 

if lst == 0 or lst == 1:
        return [lst]

 

그래서 flatten_list함수의 최상단에 다음 조건문을 삽입해서 예외처리를 해주었다.

???

그리고 실행을 해주었는데 값이 생각과 다르게 출력이 되었다. 아마도 데이터의 타입이 변경되지않은것같다.

 

def flatten_list(lst):
    if lst == 0 or lst == 1:
        return [int(lst)]

 

위의 구문을 수정해서 리턴값을 int로 바꿔주었다.

 

드디어 성공!

 

 

import numpy as np

def is_uniform(array):
    return np.all(array == array[0, 0])
    
def quadtree(array):
    
    if is_uniform(array):
        return array[0, 0]
    else:
        l = array.shape[0] // 2
        top_left = array[:l, :l]
        top_right = array[l:, :l]
        lower_left = array[:l, l:]
        lower_right = array[l:, l:]
        
        return [
            quadtree(top_left),
            quadtree(top_right),
            quadtree(lower_left),
            quadtree(lower_right)
        ]
        
def flatten_list(lst):
    if lst == 0 or lst == 1:
        return [int(lst)]
    result = []
    for i in lst:
        if isinstance(i, list):
            result.extend(flatten_list(i))
        else:
            result.append(int(i))
    return result
        
def solution(arr):
    arr = np.array(arr)
    quadtree_arr = quadtree(arr)
    quadtree_arr = flatten_list(quadtree_arr)
    
    len_arr = len(quadtree_arr)
    arr_in_one = sum(quadtree_arr)
    
    answer = [len_arr - arr_in_one, arr_in_one]

    return answer

 

많이 돌아왔지만 결국 실행에 성공은 했다. 다만 아쉬운점도 많았다. 함수를 많이 사용해서 코드가 너무 길어졌다던지... 
그래도 numpy를 연습해 볼 수 있던것은 좋았다. 데이터의 타입이 달라지기때문에 신경쓸 부분이 많아지긴했지만 배열을 다루는 것에은 아주 편리한 도구였다.