프로그래머스 쿼드 압축 (python, 파이썬)

• 문제 설명

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 입니다.

---

• 입/출력

arr	result
[[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]

---

• 코드

def check(x, y, n, arr):
    
    if n == 1:
        temp = [1, 0] if arr[x][y] == 0 else [0, 1]
        return temp
    
    left_up = check(x, y, n//2, arr)
    right_up = check(x, y+n//2, n//2, arr)
    left_down = check(x+n//2, y, n//2, arr)
    right_down = check(x+n//2, y+n//2, n//2, arr)
    
    if left_up == right_up == left_down == right_down == [0, 1] or left_up == right_up == left_down == right_down == [1, 0]:
        return left_up
    
    else:
        return list(map(sum, zip(left_up, right_up, left_down, right_down)))

def solution(arr):
    result = check(0, 0, len(arr), arr)
        
    return result

재귀함수를 이용해서 왼쪽위의 정사각형이 길이가 1인 셀이 될때까지 만든 이후에 개수를 카운트 해주는 것이다.

말로하면 어려우니 그림을 첨부합니다!!

 

마지막에 최종적으로 사각형 각 4부분을 더해주면된다. zip함수와 map함수는 중요하니 꼭 기억해두세요.!

zip함수로 list를 한번에 묶어준 이후에 map함수를 통해 각각 list의 합을 적용해서 결과를 구했습니다!

 

재귀는 알면 정말 쉬운데 코드 짜는게 아직 저한테는 많은 노력이 필요하네요ㅠㅠ

---

• 출처

programmers.co.kr/learn/courses/30/lessons/68936?language=python3