[프로그래머스][누적합] 📍쿼드압축 후 개수 세기

쿼드압축 후 개수 세기

프로그래머스

 

• 내 풀이
  • 누적합 문제
  • 처음에 check() 함수를 bfs돌면서 처리했더니 시간초과남
  • 그냥 해당 부분만 for문으로 처리하는게 시간복잡도는 동일해도 실행속도가 빠르다
    • BFS 기반이라 큐 연산의 오버헤드가 커서 실제로는 실행 시간이 더 느릴 수 있다.

1. 누적합 배열 생성
   • 배열의 누적합을 미리 계산해 블록 내 합을 빠르게 조회
2. 가장 큰 블록부터 탐색 시작
   • 블록 크기 m = n부터 시작해 /2씩 나눠가며 블록 검사
3. 블록 판별 조건
   • 블록의 합이 0: 모두 0
   • 블록의 합이 m²: 모두 1
   • 둘 다 아니면 → 더 작은 블록으로 분할
4. 처리된 블록은 기록
   • completed 배열을 사용해 이미 처리한 블록은 건너뜀

from collections import deque

def solution(arr):
    n=len(arr)
    answer = [0,0]
    
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    completed=[[False for _ in range(n)] for _ in range(n)]    
    prefix_sum=[[0 for _ in range(n+1)] for _ in range(n+1)]

    def check(i,j, dist):
        for x in range(i, i + dist):
            for y in range(j, j + dist):
                completed[x][y] = True
    
    for i in range(1,n+1):
        for j in range(1,n+1):
            prefix_sum[i][j]=prefix_sum[i-1][j]+prefix_sum[i][j-1]-prefix_sum[i-1][j-1]+arr[i-1][j-1]
    
    m=n
    while m >=1:
        for i in range(n,0,-m):
            for j in range(n,0,-m):
                if completed[i-1][j-1]:
                    continue
                tmp=prefix_sum[i][j]-prefix_sum[i-m][j]-prefix_sum[i][j-m]+prefix_sum[i-m][j-m]
                
                if tmp==0 or tmp==m**2:
                    answer[arr[i-1][j-1]]+=1
                    check(i-m,j-m,m)
        m//=2
    
    return answer