[프로그래머스] 쿼드압축 후 개수 세기 [월간 코드 챌린지 시즌1] #파이썬 #분할정복 #divide_and_conquer #재귀

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

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

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

입출력 예

[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

arr result

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

풀이

문제가 방법을 지시해주고 구현하는 방식의 문제입니다. 이러한 방식의 문제는 보통 Level 2로 책정되고, Level 3 이상부터는 문제 상황만 준 뒤 방법을 고안하는 식의 문제가 주로 출제되는 것 같습니다.

• 정사각형 영역 S를 순회하며 1의 개수, 0의 개수를 카운팅 합니다.
• 모든 수가 같은 값인지 확인합니다.
  • 같은 값이 아니면 S를 다시 정사각형 영역으로 사등분하여 확인합니다.
  • 모두 같은 값이라면 해당 값으로 압축할 수 있습니다. (0 또는 1)
    • 모두 0이면 => 0의 개수는 1, 1의 개수는 0
    • 모두 1이면 => 0의 개수는 0, 1의 개수는 1

문제를 작은 단위의 문제로 쪼개어 생각하는 divide and conquer 방식으로 보입니다. 재귀함수로 구현하여 초기값과 다른 값을 발견했을 때 영역을 재분할 하면 좋을 것 같습니다.

def quadZip(xs, ys, n):
    subtotal = [0, 0]
    init = matrix[ys][xs]
    for y in range(ys, ys+n):
        for x in range(xs, xs+n):
            if matrix[y][x] == 0:
                subtotal[0] += 1
            else:
                subtotal[1] += 1
            
            if init != matrix[y][x] and n > 2:
                subtotal = [0, 0]
                z, o = quadZip(xs, ys, n//2)
                subtotal[0] += z; subtotal[1] += o
                
                z, o = quadZip(xs+n//2, ys, n//2)
                subtotal[0] += z; subtotal[1] += o
                
                z, o = quadZip(xs, ys+n//2, n//2)
                subtotal[0] += z; subtotal[1] += o
                
                z, o = quadZip(xs+n//2, ys+n//2, n//2)
                subtotal[0] += z; subtotal[1] += o
                break
        else:
            continue
        break
        
    if subtotal[1] == 0:
        return [1, 0]
    if subtotal[0] == 0:
        return [0, 1]
    return subtotal

def solution(arr):
    global matrix
    matrix = arr
    return quadZip(0, 0, len(arr))

함수 quadZip은 x의 시작점, y의 시작점, 크기 n을 파라미터로 가지며,
변수 matrix는 solution 함수에 파라미터로 주어진 배열 arr을 가리키는 전역 변수입니다.

재귀 함수를 이용한 풀이는 언제나 발상이 어려운 것 같습니다.