[프로그래머스] 쿼드압축 후 개수 세기(Python) - 재귀

1. 문제 설명

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

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

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

 

---

2. 제한사항

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

 

---

3. 입출력 예

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]

 

 

---

4. 나의 풀이

요놈.. 문제 푸는 것보다 리팩토링에 시간을 더 썼다. 코드는 잘 돌아갔지만, 반복된 코드가 많고 가독성이 안좋았기 때문이다! 지금도 사실 가독성은 썩 좋진 않지만 코드 길이는 약 절반 정도로 줄였다. 🙃

 

쿼드 트리라는 약간은 생소한 자료구조를 활용해 만든 문제이다. 이진 트리와 달리 쿼드 트리는 거의 본적이 없기 때문에 우선 위키피디아를 정독하고 문제를 풀었다. 처음에는 트리 글자만 보고 해시를 써야하나..? 생각을 했는데 읽어보니 같은 과정을 여러번 반복해서 압축하는 부분이 핵심이었다. 재귀를 활용해보기로 했다.

 

def solution(arr):  
    if len(set(sum(arr, []))) == 1:
        return [1,0] if arr[0][0] == 0 else [0,1]

    n = len(arr) // 2
    splittedArray = []
    splittedArray.append([i[:n] for i in arr[:n]])
    splittedArray.append([i[n:] for i in arr[:n]])
    splittedArray.append([i[:n] for i in arr[n:]])
    splittedArray.append([i[n:] for i in arr[n:]])
    
    sols = []
    for i in splittedArray:
        sol = solution(i)
        if len(set(sum(i, []))) == 1:
            if i[0][0] == 0:
                sol = [1,0]
            else:
                sol = [0,1]
        sols.append(sol)
        
    return [sum([i[0] for i in sols]), sum([i[1] for i in sols])]

 

풀이의 키 포인트는 다음과 같다.

 

2차원 배열을 4개로 쪼갠 후, 각각의 배열에 대해 재귀 함수 호출한 결과를 더하여 리턴한다.

 

결과적으로 이 함수의 인풋은 2차원 정수 배열, 아웃풋은 [0의 개수, 1의 개수]가 된다. 또한, 쿼드 트리의 핵심이라고 볼 수 있는 같은 수 압축 과정은 함수 가장 맨 처음에 확인해준다.

 

    if len(set(sum(arr, []))) == 1:
        return [1,0] if arr[0][0] == 0 else [0,1]

 

재귀적으로 문제 해결하는 것은 늘 어렵다. 또, 무작정 쓰려다가 오히려 호출 횟수가 급격히 늘어날 경우 오버플로우가 발생할 수도 있다. 적절한 상황에 맞게 활용해야한다..

 

 

 

문제 링크: programmers.co.kr/learn/courses/30/lessons/68936

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