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

https://programmers.co.kr/learn/courses/30/lessons/68936

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

이 문제는 grid와 stack을 이용해서 풀었다.

 

사각형으로 구성된 모든 값이 0이나 1이 될때 까지 계속 stack으로 쌓았다.

어차피 하나의 block으로 구성된 것은 0, 1로만 구성될 것이다.

이 방식으로 네개로 쪼갤 수 있는 방식으로 생각을 했다.

 

이 문제의 keypoint는 중간값을 이용해서 네개로 나누는 것이다. 이것을 사용하면 다양한 방법으로 풀 수 있다

def solution(arr):
    n = len(arr)
    # 0, 1 횟수 세기
    asw_0 = 0
    asw_1 = 0
    # 스텍을 이용해서 grid 탐색
    stack = [[0, n, 0 , n]]
    while stack:
        si, ei, sj, ej = stack.pop()
        # 중간값 찾기
        midi = (si+ei)//2
        midj = (sj+ej)//2
        # 1의 갯수 구하기
        total_sum = 0
        for i in range(si, ei):
            for j in range(sj, ej):
                if arr[i][j]:
                    total_sum += 1
        # 만약 총합이 현재 grid의 block 갯수 만큼있다면 asw_1 += 1
        if total_sum == (ei-si) ** 2:
            asw_1 += 1
        # 총합이 0이면 다 0이라는듯
        elif not total_sum:
            asw_0 += 1
        # 아니면 4방향 분해해서 stack에 담기
        else:
            stack.append([si, midi, sj, midj])
            stack.append([si, midi, midj, ej])
            stack.append([midi, ei, sj, midj])
            stack.append([midi, ei, midj, ej])

    answer = [asw_0, asw_1]
    return answer