[PROGRAMMERS] 월간 코드 챌린지 시즌 1 : 쿼드압축 후 개수 세기 Python

알고리즘 스터디를 준비하며 풀게 된 문제이다. 물론 어려운 문제였지만 이때까지 완전 검색과 DFS를 풀면서 많이 봤던 유형이었기 때문에 어떻게 풀지 비교적 쉽게 방향을 잡을 수 있었다.

문제를 간략히 설명하자면, 배열이 주어졌을 때, 그 배열을 정사각형으로 나누고, 그 정사각형이 모두 같은 값이면 하나로 압축할 수 있고 이렇게 압축했을 때 배열의 최종적으로 남는 0의 개수와 1의 개수를 출력하는 문제이다.

이 문제에서 제공하는 그림을 본다면,

가장 왼쪽 사각형처럼 초기배열 상태에서는 모든 수가 같지 않기 때문에 2^(1/2) 배수로 정사각형을 나눠야 하고, 그렇게 나누어진 게 두 번째 사각형이다. 두 번째 사각형에서는 1 사분면의 값이 모두 같아지기 때문에 0으로 압축할 수 있다. 이 과정은 정사각형의 크기가 1이 될 때까지 반복할 수 있는데, 정사각형의 크기가 1이 된다면 더 이상 사각형의 크기를 줄일 수 없게 된다.

큰 하나의 사각형을 검사하고, 이를 네 개로 분할하여 각각 검사하고 값이 나오면 return 아니면 또 네개로 분할... 이 과정이 '나는 완전 검색 문제야!'라고 말해주는 것 같았기 때문에 우선 N의 크기를 확인해 보았는데, 1024 즉, 2^10. 분할하는 과정이 최대 10번이면 완전 검색으로 해도 시간상 넉넉할 것 같다는 생각이 바로 구현해 보았다.  

코드로 나타낸다면,

def solution(arr):
    def check(si, sj, ei, ej):
        nonlocal answer
        if si >= ei - 1 or sj >= ej - 1:
            answer[arr[si][sj]] += 1
            return

        mid_i = (ei + si) // 2
        mid_j = (sj + ej) // 2
        stand = arr[si][sj]
        flag = 0

        for i in range(si, ei):
            for j in range(sj, ej):
                if stand != arr[i][j]:
                    flag = 1


        if flag:
            check(si, sj, mid_i, mid_j)
            check(si, mid_j, mid_i, ej)
            check(mid_i, sj, ei, mid_j)
            check(mid_i, mid_j, ei, ej)


        else:
            answer[stand] += 1
    answer = [0] * 2
    si = sj = 0
    ei = ej = len(arr)
    check(si,sj,ei,ej)

    return answer

 이렇게 된다.

코드로 구현할 때, 헷갈렸던 부분이 

이 부분이었다. 즉, 사각형을 검사했을 때, 사각형의 모든 값이 같지 않다면(flag==true) 사각형을 네 개로 쪼개어 재귀 함수로 들어가야 하는데 이 조건 분기가 생각보다 까다로웠다.

나는 행의 중간값과, 열의 중간 값을 미리 구하여
    1. 시작행, 열은 그대로고 끝 행, 열이 중간값으로 바뀌는 함수
    2. 시작행은 그대로, 끝행은 중간값으로 바뀌고 / 시작 열은 중간부터, 끝 행은 그대로인 함수
    3. 시작행은 중간값, 끝행은 그대로, 시작 열은 그대로, 끝열은 중간값인 함수
    4. 시작행, 열은 중간 값/ 끝행, 열은 그래도 인 함수
이렇게 네 개의 함수로 재귀를 시켰다.

그래도 익숙한 유형이라고 생각하여, 손 코딩 과정을 하지 않고 풀었는데 이런 조건 분기 부분에서 헷갈려서 시간을 많이 쓴 것 같다.

오늘도 한 번 더 손 코딩의 중요성을 느낀다.

하루 한 개 알고리즘 파이팅!

 

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/68936

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