[코드잇,divide and Conquer] merge 함수 python

merge함수.py

divide and Conquer
1.divide
2.conquer
3.combine

def merge(list1, list2):
    result = []

    # 길이가 0일때나 1일때는 divide를 안해도 된다~
    if len(list1) == 0:
        result = merge(list2, list2[int(len(list2) / 2):int(len(list2))])
        return result
    if len(list2) == 0:
        result = merge(list1, list1[int(len(list1) / 2):int(len(list1))])
        return result

    if len(list1) == 1 and len(list2) == 1:
        if list1[0]>list2[0]:
            return list2[:1]+list1[:1]
        elif list1[0]<list2[0]:
            return list1[:1] + list2[:1]
        else:
            return list1[:1]

    
    
    # Combine을 위한 변수 left,right
    result_left = []
    result_right = []


    # 문제해결을 위해 divide 하는 부분
    mid1 = int(len(list1) / 2)
    mid2 = int(len(list2) / 2)
    
    #재귀 부분
    result_left = merge(list1[0:int(len(list1) / 2)], list1[int(len(list1) / 2):int(len(list1))])
    result_right = merge(list2[0:int(len(list2) / 2)], list2[int(len(list2) / 2):int(len(list2))])
    # 재귀 부분
    
    # 문제해결을 위해 divide 하는 부분

    # 나온 결과값을 토대로 Combine 하는곳!
    totalLen = int(len(result_right)+len(result_left))
    
    for i in range(0, totalLen):

        if len(result_left)>0 and len(result_right)>0:
            if result_left[0] > result_right[0]:
                result.append(result_right[0])
                result_right.remove(result_right[0])
            else:
                result.append(result_left[0])
                result_left.remove(result_left[0])
        elif len(result_left) == 0:
            result.append(result_right[0])
            result_right.remove(result_right[0])
        elif len(result_right) == 0:
            result.append(result_left[0])
            result_left.remove(result_left[0])

    return  result



# 코드를 작성하세요.

# 테스트
# print(merge([1], []))
# print(merge([], [1]))
# print(merge([2], [1]))
print(merge([1, 2, 3, 4], [5, 6, 7, 8]))
# print(merge([5, 6, 7, 8], [1, 2, 3, 4]))
# print(merge([4, 7, 8, 9], [1, 3, 6, 10]))