[프로그래머스] 쿼드압축 후 개수 세기 (코딩테스트 연습 | 월간 코드 챌린지 시즌 1)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

---

아이디어

✅ 사각형을 4개로 나눈다

• ✅ 재귀함수를 이용해 구현
• 사각형의 가로, 세로가 1이 될때까지 또는 사각형 내 숫자가 모두 같을 때까지 반복수행

---

코드

def divide_square(arr):
    length = len(arr[0])
    arr_1 = [[0] * (length//2) for _ in range(length//2)]
    arr_2 = [[0] * (length//2) for _ in range(length//2)]
    arr_3 = [[0] * (length//2) for _ in range(length//2)]
    arr_4 = [[0] * (length//2) for _ in range(length//2)]
    
        
    for r in range(length):
        for c in range(length):
            if r < length//2 and c < length//2:
                arr_1[r][c] = arr[r][c]
                
            elif r < length/2 and c >= length/2:
                arr_2[r][c-length//2] = arr[r][c]
                
            elif r >= length/2 and c < length/2:
                arr_3[r-length//2][c] = arr[r][c]
                
            elif r >= length/2 and c >= length/2:
                arr_4[r-length//2][c-length//2] = arr[r][c]
                
    return arr_1, arr_2, arr_3, arr_4
    
num_0 = 0
num_1 = 0

def check(arr):
    global num_0
    global num_1
    
    length = len(arr[0])
    temp = arr[0][0]
    
    if length == 1:
        if temp == 0:
            num_0 += 1
        elif temp == 1:
            num_1 += 1
        return
    
    # 수가 전부 같다면 0
    flag = 0
    
    # 수가 전부 같은지 확인
    for r in range(length):
        for c in range(length):
            if temp != arr[r][c]:
                flag = 1
                break
    
        if flag == 1: # 수가 다름
            break
    
    # 수가 다른 경우
    if flag == 1:
        divide_arrs = divide_square(arr)
        for divide_arr in divide_arrs:
            check(divide_arr)
    
    # 수가 전부 같은 경우    
    else:    
        if temp == 0:
            num_0 += 1
        elif temp == 1:
            num_1 += 1
                    

def solution(arr):
    global num_0
    global num_1
    
    answer = []

    check(arr)
    
    answer = [num_0, num_1]
    return answer

 

 

 

---

풀이 후

 

✅ all 함수

• 파이썬 내장 함수, 모든 요소가 참일 때만 True 반환
• 수가 전부 같은지 확인하는 코드 단축 가능

first_element = arr[0][0]
    
all_same = all(arr[r][c] == first_element for r in range(length) for c in range(length))

# all_same은 True 혹은 False
# all_same 값에 따라 flag 없이 분기 가능 (divide_square 혹은 중단)