[파이썬] 쿼드압축 후 개수 세기

문제 설명

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]

---

입출력 예 설명

입출력 예 #1

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

• 

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

입출력 예 #2

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

• 

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

 

✨ 나의 풀이

def solution(arr):
    answer=[]
    
    def dfs(s, e, size) :
        value=arr[s][e]
        for i in range(s, s+size) :
            for j in range(e, e+size) :
                if arr[i][j] != value :
                    half=size//2
                    dfs(s, e, half)		# 1사분면
                    dfs(s, e + half, half)	# 2사분면
                    dfs(s + half, e, half)	# 3사분면
                    dfs(s + half, e + half, half)	# 4사분면
                    return
        answer.append(value)
    
    dfs(0, 0, len(arr))

    return [answer.count(0), answer.count(1)]   # [최종 0의 개수, 최종 1의 개수]

다른 사람 풀이 참고

DFS 재귀

같은 값이 연속되지 않으면 범위를 절반으로 줄여서 재귀 호출

 

 

★ 다른 사람 코드

def solution(arr):
    def merge(p, q, size):
        value=arr[p][q]
        for i in range(p, p+size):
            for j in range(q, q+size):
                if arr[i][j] != value:
                    merge(p, q, size//2)
                    merge(p, q+size//2, size//2)
                    merge(p+size//2, q, size//2 )
                    merge(p+size//2, q+size//2, size//2 )
                    return
        answer.append(value)
    
    answer = []            
    merge(0, 0, len(arr))   # 함수 호출
    return [answer.count(0), answer.count(1)]

 

문제를 작게 쪼개기 때문에 merge algorithm을 쓰면 된다.

 

★ arr=[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]을 예로 실행과정 설명

처음에 j가 2까지 갔다가 if가 true돼서 merge(p, q, size//2)를 실행함. arr[1][2]=0때문에 true돼서 merge(p, q, size//2)실행. size=1임.  자기 자신끼리 비교하므로 answer에 하나씩 다 append됨. merge()가 순차적으로 실행됨.

끝나면 return한 후에 merge(p, q+size//2, size//2)가 실행됨. merge(l, r, s)가 실행됐었으니까.

value=arr[0][2]임.  arr[0][3], arr[1][2], arr[1][3] 다 똑같아서 answer에 0을 append한다. merge(p+size//2, q, size//2)호출. 

value[2][0]이다. 이런식으로 반복됨.

 

재귀를 이용해서 해결한다. 배열 길이의 반만큼 인덱스에 더한 것으로 사각형으로 자른 것처럼 된다. 

길이가 4인 경우 [0, 0]에서 [1, 1]까지

[0, 2]에서 [1, 3]까지

[2, 0]에서 [3, 1]까지

[2, 2]에서 [3, 3]까지로 재귀가 이루어짐.

 

def solution(arr):
    answer = [0, 0]
    length=len(arr)
    
    def comp(p, q, size):
        value=arr[p][q]
        for i in range(p, p+size):
            for j in range(q, q+size):
                if arr[i][j] != value:
                    _size=size//2
                    comp(p, q, _size)
                    comp(p, q+_size, _size)
                    comp(p+_size, q, _size)
                    comp(p+_size, q+_size, _size)
                    return
        answer[value]+=1
    comp(0, 0, length)
    return answer

 

value가 0또는 1이니까 answer[value]를 1씩 증가시키는게 신박했다. 깔끔한 코드다.

 

def solution(arr):
    def check(y, x, n):
        if n==1:		# 길이가 1일 때
            return [0,1] if arr[y][x]==1 else [1,0]
        left=check(y, x, n//2)
        right=check(y, x+n//2, n//2)
        l_down=check(y+n//2, x, n//2)
        r_down=check(y+n//2, x+n//2, n//2)
        
        if left==right==l_down==r_down==[0, 1] or left==right==l_down==r_down==[1, 0]:
            return left
        else:
            return list(map(sum, zip(left, right, l_down, r_down)))
    answer=check(0, 0, len(arr))
    return answer

 

 

 

문제 출처 👉 프로그래머스