프로그래머스 2단계 - 쿼드 압축 후 개수 세기

문제 설명

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

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

• 

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

입출력 예 #2

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

• 

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

---

접근법

다른 쿼드트리 문제를 divide and conquer 방법으로 푼 기억이 있다. 이 문제도 같은 방식으로 접근하였다.

 

먼저 가장 작은 단위에서 일어나는 일을 보자.

 

(1) 최종적으로 남은 것이 0이라면 [1,0] 을 리턴해주고, 남은 것이 1이라면 [0,1]을 리턴해준다.

 

이 과정을 큰 단위에서 작은 단위로 가면서 구현되는 함수를 만들어야 한다.

 

(2) 점점 줄어드는 단위를 설정한 후 

 

(3) 재귀를 통해서 (1)과 (2)가 반복적으로 Divide되면서 이루어진 후 최종적으로 리턴된 값을 Conquer 해주면 된다.

---

코드

import numpy as np
def solution(arr):
    def divide(s):
        if np.all(s==0): # 최종적으로 남은 것이 0일 때
            return np.array([1,0])
        if np.all(s==1): # 최종적으로 남은 것이 1일 때
            return np.array([0,1])
        
        x = s.shape[0]//2 # 다음번째로 Divide할 단위
        
        # Conquer
        return divide(s[:x,:x]) + divide(s[:x,x:]) + divide(s[x:,:x]) + divide(s[x:,x:])
    return divide(np.array(arr)).tolist()

---

풀이

    def divide(s):
        if np.all(s==0): # 최종적으로 남은 것이 0일 때
            return np.array([1,0])
        if np.all(s==1): # 최종적으로 남은 것이 1일 때
            return np.array([0,1])

numpy 의 all()을 이용하여 하나의 단위 안의 수가 0인지 1인지 확인할 수 있다.

그리고 나중에 Conquer 해줄 것이기 때문에 [1,0] 또는 [0,1] 을 리턴해준다.

 

        x = s.shape[0]//2 # 다음번째로 Divide할 단위

numpy의 shape()를 이용하면 array가 몇차원인지 확인할 수 있으며,

점점 줄어드는 단위 x를 가장 첫 차원을 2로 나누어준 것으로 설정해준다.

 

        return divide(s[:x,:x]) + divide(s[:x,x:]) + divide(s[x:,:x]) + divide(s[x:,x:])

가장 작은 단위로 나누어지면서 [1,0] 또는 [0,1]로 리턴되므로 이 값들을 더해준다.

 

def solution(arr):
	return divide(np.array(arr)).tolist()

이제 이 함수에 numpy의 array 형식으로 배열을 넣어준 후 리스트로 바꾸어 준다면 원하는 값을 얻을 수 있다.

 

numpy의 기능을 잘 활용할 줄 안다면 복잡해보이는 내가 어려워하는 리스트 문제도 직관적이며 간단하게 해결할 수 있다는 것을 알았다.