[Programmers] Level 2. 쿼드압축 후 개수 세기

🔗 Problem Link

프로그래머스

---

❔Thinking

• 0과 1로 이루어진 정수 배열 arr을 작게 나누어, 나뉜 영역이 모두 0이거나 1이면 해당 수 하나로 압축한다.
• 나뉜 영역이 압축 불가하다면, 다시 작게 나누어 확인하는 과정을 반복한다.
• 압축 시행 후, 0과 1의 개수를 각각 세어 반환한다.

문제를 다음과 같이 생각할 수 있다.

크기가 $2^{n}$인 0 또는 1로만 이루어진 도장을 만들고, 이 도장과 모양이 같을 경우 판에 도장을 찍는다.
0의 도장과 1의 도장이 각각 찍힌 횟수 반환한다.

 

---

 

 

💻Solution

def QuadStamp(arr:list, N:int)->list:
    result = [0,0]
    for x in range(0, len(arr), N):
        for y in range(0, len(arr[0]), N):
            zero_stamp = True
            one_stamp = True
            for i in range(x, x+N):
                for j in range(y, y+N):
                    if arr[i][j] != 0: zero_stamp = False
                    if arr[i][j] != 1: one_stamp = False
            if zero_stamp is True or one_stamp is True:
                for i in range(x, x+N):
                    for j in range(y, y+N):
                        arr[i][j] = '-'
            result[0], result[1] = result[0]+zero_stamp, result[1]+one_stamp
    return arr, result
    
    
def solution(arr):
    answer = [0, 0]
    # 0과 1개수 세기
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == 0: answer[0] += 1
            if arr[i][j] == 1: answer[1] += 1
    # 스탬프 찍어보기
    stamp_size = len(arr)
    while stamp_size > 1:
        arr, tmp = QuadStamp(arr, stamp_size)
        answer[0] -= tmp[0] * (stamp_size**2 - 1)
        answer[1] -= tmp[1] * (stamp_size**2 - 1)
        stamp_size //= 2
    return answer

---

🗝️keypoint

1. 압축 시행 후 0과 1의 개수는, 전체 0과 1의 개수에서 압축이 가능한 경우를 뺀 값과 같다.
2. 이미 압축이 이루어진 경우, 더 작은 단위의 도장으로 압축되지 않도록 제외시키는 알고리즘이 필수적이다.
3. 큰 영역에서 작은 영역으로 압축 가능 여부를 확인해야 더 적은 반복으로 원하는 값을 얻을 수 있다.