프로그래머스 / 분할정복 / 쿼드압축 후 개수 세기

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

0 과 1로 이뤄진 배열을 쿼드압축하여 [0의 개수, 1의 개수]로 리턴하여라.

 

쿼드압축은 다음과 같은 순서로 이뤄진다.

 

1. 현재 정사각형의 내부가 모두 같은 수라면 한 값으로 압축한다.

2. 그렇지 않다면 4개의 균일한 정사각형으로 쪼갠다.

3. 그렇지 않은 4개의 정사각형을 1번 과정부터 다시 진행한다.

 

이런 문제들은 분할정복 문제로 절대적인 위치가 아닌 상대적 위치로 코딩을 해줘야 한다.

 

일단 첫 번째로 영역의 0, 1의 개수는 먼저 세주었다.

그 후 0 또는 1 중 하나라도 0이라면 리턴하게끔 base-condition을 짰다.

 

그렇지 않다면 4개의 구간으로 나누는데,

시작 x, y부터 끝나는 ex, ey라고 했을 때 구간의 총 개수를 2로 나눠서 

좌측 상단, 우측 상단, 좌측 하단, 우측 하단으로 구간을 나누었다.

 

그 후 각 갯수를 세서 리턴해주었다.

정답코드

---

'''
'25. 11. 13.(목)

1. 0과 1로 이뤄진 2^n * 2^n 배열이 있다.

1. S 내부에 있는 모든 수가 같은 값이라면, 한 값으로 압축한다.
2. S를 정확히 4개의 균일한 정사각형 영역으로 쪼갠다.

최종적으로 [0의 개수, 1의 개수] 리턴

분할정복으로 문제를 풀이하면 될 듯 싶다.
시작 x, y
끝 x, y를 리턴한다.
'''
#
def quad_compression(sx: int, sy: int, ex: int, ey: int, board: list) -> list:
    ret = [0, 0]
    for row in range(sx, ex):
        for col in range(sy, ey):
            ret[board[row][col]] += 1
    
    #둘 중 하나가 0이라면 바로 리턴
    if ret[0] == 0 or ret[1] == 0:
        return [+(ret[0] > 0), +(ret[1] > 0)]
    
    alpha = (ex - sx) >> 1
    ret1 = quad_compression(sx, sy, sx + alpha, sy + alpha, board)
    ret2 = quad_compression(sx, sy + alpha, sx + alpha, ey, board)
    ret3 = quad_compression(sx + alpha, sy, ex, sy + alpha, board)
    ret4 = quad_compression(sx + alpha, sy + alpha, ex, ey, board)
    
    
    for i in range(2):
        ret[i] = ret1[i] + ret2[i] + ret3[i] + ret4[i]
    
    return ret
def solution(arr):
    answer = quad_compression(0, 0, len(arr), len(arr), arr)
    return answer

 

깃허브 : https://buly.kr/ESzRxOG

유튜브 : https://youtu.be/zVk9GfPF54g