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

문제) 쿼드압축 후 개수 세기

프로그래머스

 

주어진 문제로는 0, 1로 이루어진 정 사각형(2**n X 2**n)에서 정사각형으로 나눈 뒤에 해당 영역에 0 또는 1로만 이루어졌다면 압축 하는 방식으로 최종 압축 후의 0의 개수와 1의 개수를 각각 배열에 담아 리턴 해주는 함수를 만드는 문제였다.

 

접근 방식

1. 2의 제곱으로 이루어졌다고 하였고 압축도 2의 제곱이기에 전체 크기를 2로 나누어 가면 될거 같다

2. 파이썬에서 배열을 나눌때에는 a[k:m]형식으로 나눌수 있으나 이는 1차원 배열에만 적용 가능, 2차원 배열에다 동일한 방식으로 나눌려면 numpy 모듈을 사용이 필요(물론 이걸 하드 코딩하는 방식이 있고 그렇게 풀 수도 있지만 numpy를 안다면 괜히 고생할 필요도 없으니 모듈을 사용합시다)

3. 나누어진 곳에서 값들의 개수를 센 후 값들이 전부 동일하면 한개를 제외한 나머지는 -1과 같은 필요 없는 수로 대체

3.1. numpy는 array 형식이기에 개수를 셀려면 형변환이 필요하나 numpy에서 제공하는 함수중 unique를 통하여 갯수를 셀 수이다

3.2 만약 unique를 모른다고하면 list로 형변환 한뒤(numpy.tolist()) count()혹은 for문을 배회하며 를 통하여 문자를 셀 수 있다.

4. 최종적으로 큰 배열에서 작은 배열까지 전부 조회 후 전체 수를 카운트

 

1 차 코드

import numpy as np
from collections import Counter
def solution(arr):
    answer = []
    k = len(arr) // 2
    while k > 1:
        np_arr = np.array(arr)
        for i in range(0, len(arr), +k):
            for j in range(1, (len(arr) // k) + 1):
                print(np_arr[i: i + k, (j - 1) * k: j * k])
                value, count = np.unique(np_arr[i: i + k, (j - 1) * k: j * k], return_counts=True)
                if len(count) == 1 and value != -1:
                    is_ok = False
                    for x in range(i, i+k):
                        for y in range((j - 1) * k, j * k):
                            if not is_ok:
                                is_ok = True
                                continue
                            arr[x][y] = -1
        k //= 2
    num_counter = Counter(sum(arr, []))
    answer = [num_counter[0], num_counter[1]]
    return answer

해당 코드는 일단 먼저 2로 나누어 진행하는 방식으로 진행하였다.

그런데 이렇게 먼저 2로 나누어 진행하게 될 경우 

[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]의 배열이 주어졌다고 하면 답으로 [0, 1]이 나와야 되는데 [0, 4]가 나오게 된다

그렇기에 처음에는 전체 크기에서 확인이 필요

최종 코드

import numpy as np
from collections import Counter
def solution(arr):
    answer = []
    k = len(arr)
    while k > 1:
        np_arr = np.array(arr)
        for i in range(0, len(arr), +k):
            for j in range(1, (len(arr) // k) + 1):
                print(np_arr[i: i + k, (j - 1) * k: j * k])
                value, count = np.unique(np_arr[i: i + k, (j - 1) * k: j * k], return_counts=True)
                if len(count) == 1 and value != -1:
                    is_ok = False
                    for x in range(i, i+k):
                        for y in range((j - 1) * k, j * k):
                            if not is_ok:
                                is_ok = True
                                continue
                            arr[x][y] = -1
        k //= 2
    num_counter = Counter(sum(arr, []))
    answer = [num_counter[0], num_counter[1]]
    return answer

 

이렇게 처음 문제를 접했을 때에는 막막해 보였던 문제가 차분히 생각을 정리하면서 코드를 작성하다 보니 무난하게 풀리게 되었다

 

물론 numpy 나 Counter 모듈을 사용하지 않았다면 코드가 길어지기도 하겠지만 다행히 지난 코드카타를 진행하면서 파이썬 문법은 물론 여러가지 모듈을 알게 되어 문제 난이도가 조금은 내려간것 같다

앞으로 꾸준히 문제를 풀어가며 실력을 쌓아야 겠다

목표는 일단 내일배움캠프에서 준 알고리즘 코드카타 정복이며 최종적으로는 프로그래머스 문제(Lv.3 정복) 및 백준 문제(단계 로 되어있는 부분 전부 풀기)를 최대한 많이 풀어볼 생각이다