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

프로그래머스 '쿼드 압축 후 개수 세기' 문제 풀이입니다.

 

문제 링크

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

 

● 문제 간단 설명

주어진 2차원 배열에 대해서 4개의 영역으로 나누었을 때 한 영역 내부에 요소가 모두 1이거나 0일 경우 그 영역을 1이나 0으로 치환한다. 4개의 영역의 크기가 1이 될 때까지 나누는 과정과 치환하는 과정을 반복한다고 할 때 반복이 모두 끝났을 때 0과 1의 개수를 구하는 문제.

 

● 문제 해결 방향

프로그래머스 - 쿼드압축후 개수 세기 예시 이미지

4개의 영역으로 나누고, 각 영역에 대해서 모든 요소가 1 또는 0인지를 판단하는 과정이 계속 반복되기 때문에 재귀함수를 활용해서 각 영역의 크기가 1이 될 때까지 반복해서 로직을 수행하도록 해주었다.

 

● 문제 해결 코드

def quadCount(arr):
    zeroCount = 0
    oneCount = 0
    if len(arr) > 1:
        halfLen = len(arr) // 2
        totalCount = sum(sum(a) for a in arr);
        if totalCount == 0:
            zeroCount += 1
        elif totalCount == len(arr) ** 2 :
            oneCount += 1
        else :
            for rowPart in range(0, len(arr), halfLen):
                for colPart in range(0, len(arr), halfLen):
                    [newZeroCount, newOneCount] = quadCount(list(map(lambda x: x[colPart:colPart + halfLen], arr[rowPart:rowPart + halfLen])))
                    zeroCount += newZeroCount
                    oneCount += newOneCount
    else:
        return [0, 1] if arr[0][0] else [1, 0]
    
    return [ zeroCount, oneCount ]
    

def solution(arr):
    return quadCount(arr)

solution

quadCount() 함수를 통해 나온 결과 값이 리턴되도록 해주었다.

 

quadCount()

각 영역에 대해서 1, 0의 숫자를 세어주는 함수로써,

영역의 가로, 세로 길이가 1인 경우 1 또는 0을 판단하여 적절한 변수의 수를 올려주었다.

영역의 가로, 세로 길이에 대해서 1이 아닌 경우에는 영역의 값이 모두 동일한지 확인하는 로직(if, elif 부분)을 거치고 아닌 경우(else), 4개의 영역으로 나누어서 quadCount()를 재귀적으로 호출하여 위와 같은 작업을 반복해주었다.

 

배열 크기에 대해서 2의 거듭제곱 수의 형태를 띄고 있다는 제약 사항 때문에 재귀 함수를 빨리 떠올려서 어렵지 않게 문제를 풀 수 있었다.

배열 크기에 대한 제약 사항이 없었다면 또 엄청 헤맸을지도...?

 

● 참고