쿼드압축 후 개수 세기 [프로그래머스]

문제링크

 

문제풀이

 

예전에 한번 문제만 봤던건데 예전과 달라진 점은 이제 그림을 보고 “오! 재귀함수로 풀면 금방 풀리겠다” 가 보이는 단계로 진화했다. 문제풀이 각이 보이니 얼른 풀었다.

입력으로 들어오는 arr 행렬을 4등분해서 갯수를 세면 되겠다 싶었다.

규칙으로는

1. arr 행렬 4등분 하기
2. arr 의 길이가 1 이라면 해당 배열의 숫자 그냥 반환하기
3. 4등분 된 각 부분의 모든 숫자가 같다면 그 숫자 하나만 반환하기 (압축)
4. 그렇게 제일 작은 부분부터 사분면 합치면서 재귀함수 빠져나오기

하나씩 구현해보자

1. arr 행렬 4등분하기

def slice_arr(arr, upDown, direction):
    temp_arr = []
    slice_num = len(arr)//2
    if upDown == "up": # 가로를 기준으로 위쪽만 보기 위함
        for sub in arr[:slice_num]:
            sub_arr = []
            if direction == "left": # 세로를 기준으로 왼쪽만 보기 위함
                for num in sub[:slice_num]: 
                    sub_arr.append(num)
                temp_arr.append(sub_arr) # 1사분면
            else:
                for num in sub[slice_num:]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr) # 2사분면
    else: # 가로를 기준으로 아래쪽만 보기 위함
        for sub in arr[slice_num:]:
            sub_arr = []
            if direction == "left":
                for num in sub[:slice_num]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr) # 3사분면
            else:
                for num in sub[slice_num:]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr) # 4사분면
    return temp_arr

1. arr 의 길이가 1 이라면 해당 배열의 숫자 그냥 반환하기
2. 4등분 된 각 부분의 모든 숫자가 같다면 그 숫자 하나만 반환하기 (압축)

def dfs(arr):
    #arr 의 길이가 1 이라면 해당 배열의 숫자 그냥 반환하기
    count_dic = {} # dictionary 형태로 반환
    if len(arr) == 1:
        count_dic[arr[0][0]] = 1
        return count_dic 
    
    else:
				# 4등분하기
        temp_arr = slice_arr(arr, "up","left")
        quater_1 = dfs(temp_arr) # 1사분면
        
        temp_arr = slice_arr(arr, "up", "right")
        quater_2 = dfs(temp_arr) # 2사분면
        
        temp_arr = slice_arr(arr, "down", "left")
        quater_3 = dfs(temp_arr) # 3사분면
        
        temp_arr = slice_arr(arr, "down", "right")
        quater_4 = dfs(temp_arr) # 4사분면 
        
				# 각 사분면의 결과들 (압축 or no압축)을 하나로 합치는 작업
        for key in quater_1.keys():
            if key in count_dic:
                count_dic[key] += quater_1[key]
            else:
                count_dic[key] = quater_1[key]
                
        for key in quater_2.keys():
            if key in count_dic:
                count_dic[key] += quater_2[key]
            else:
                count_dic[key] = quater_2[key]
                
        for key in quater_3.keys():
            if key in count_dic:
                count_dic[key] += quater_3[key]
            else:
                count_dic[key] = quater_3[key]
                
        for key in quater_4.keys():
            if key in count_dic:
                count_dic[key] += quater_4[key]
            else:
                count_dic[key] = quater_4[key]
        
				# 4등분 된 각 부분의 모든 숫자가 같다면 그 숫자 하나만 반환하기 (압축)
        key_list = list(count_dic.keys())
        if len(key_list) == 1 and count_dic[key_list[0]] == 4:
            count_dic[key_list[0]] = 1
                
        return count_dic

주의점 결과에 0 또는 1이 존재하지 않을수 있기 때문에 예외 처리를 해줘야 한다.

def solution(arr):
    answer = []
    
    count_dic = dfs(arr)
    if 0 in count_dic: # 0이 존재할때만 숫자 써주기
        answer.append(count_dic[0])
    else:
        answer.append(0)
        
    if 1 in count_dic: # 1이 존재할때만 숫자 써주기
        answer.append(count_dic[1])
    else:
        answer.append(0)
    
    return answer

결과는

 

전체 코드

def slice_arr(arr, upDown, direction):
    temp_arr = []
    slice_num = len(arr)//2
    if upDown == "up":
        for sub in arr[:slice_num]:
            sub_arr = []
            if direction == "left":
                for num in sub[:slice_num]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr)
            else:
                for num in sub[slice_num:]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr)
    else:
        for sub in arr[slice_num:]:
            sub_arr = []
            if direction == "left":
                for num in sub[:slice_num]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr)
            else:
                for num in sub[slice_num:]:
                    sub_arr.append(num)
                temp_arr.append(sub_arr)
    return temp_arr

def dfs(arr):
    count_dic = {}
    if len(arr) == 1:
        count_dic[arr[0][0]] = 1
        return count_dic
    else:
        temp_arr = slice_arr(arr, "up","left")
        quater_1 = dfs(temp_arr)
        
        temp_arr = slice_arr(arr, "up", "right")
        quater_2 = dfs(temp_arr)
        
        temp_arr = slice_arr(arr, "down", "left")
        quater_3 = dfs(temp_arr)
        
        temp_arr = slice_arr(arr, "down", "right")
        quater_4 = dfs(temp_arr)
        
        for key in quater_1.keys():
            if key in count_dic:
                count_dic[key] += quater_1[key]
            else:
                count_dic[key] = quater_1[key]
                
        for key in quater_2.keys():
            if key in count_dic:
                count_dic[key] += quater_2[key]
            else:
                count_dic[key] = quater_2[key]
                
        for key in quater_3.keys():
            if key in count_dic:
                count_dic[key] += quater_3[key]
            else:
                count_dic[key] = quater_3[key]
                
        for key in quater_4.keys():
            if key in count_dic:
                count_dic[key] += quater_4[key]
            else:
                count_dic[key] = quater_4[key]
        
        key_list = list(count_dic.keys())
        if len(key_list) == 1 and count_dic[key_list[0]] == 4:
            count_dic[key_list[0]] = 1
                
        return count_dic
        

def solution(arr):
    answer = []
    
    count_dic = dfs(arr)
    if 0 in count_dic:
        answer.append(count_dic[0])
    else:
        answer.append(0)
        
    if 1 in count_dic:
        answer.append(count_dic[1])
    else:
        answer.append(0)
    
    return answer