[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 24회차 미션

merge 함수 만들기

* 목표: left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return 하기

* left와 right는 이미 정렬된 상태 또는 데이터가 하나임

프로그래밍 연습

1. left 부터 하나씩 right과 비교

2. left > right 이면, left 를 sorted_list에 넣고, 다음 left 리스트와 right 비교

   - 그렇지않으면 반대로 하기

다음 경우만 프로그래밍으로 작성해보기

left = [0]

right = [3]

결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴

프로그래밍 연습

다음 경우만 프로그래밍으로 작성해보기

left = [0, 2]

right = [1]

결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴

프로그래밍 연습

다음 경우만 프로그래밍으로 작성해보기

left = [0, 2]

right = [1, 3]

결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴

프로그래밍 연습

left, right 리스트 변수의 데이터 수가 한 개에서 여러 개가 될 수 있을때 작성해보기(일반화)

1. sorted_list 리스트 변수 선언하기

2. left_index, right_index 를 0 으로 초기화 하기

3. while left_index < len(left) or right_index < len(right) 이면,

 - 만약 left_index >= len(left)이면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가

   - 만약 right_index >= len(right)이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가

   - 만약 left[left_index] < right[right_index]이면, sorted_list 에 left[left_index] 를 추가하고, left_index 값을 1증가

   - 위 세가지가 아니면, sorted_list 에 right[right_index] 를 추가하고, right_index 값을 1증가

 

def merge(left, right):

    merged = list()

    left_point, right_point = 0, 0

   

    # case1 - left/right 둘다 있을때

    while len(left) > left_point and len(right) > right_point:

        if left[left_point] > right[right_point]:

            merged.append(right[right_point])

            right_point += 1

        else:

            merged.append(left[left_point])

            left_point += 1

 

    # case2 - left 데이터가 없을 때

    while len(left) > left_point:

        merged.append(left[left_point])

        left_point += 1

       

    # case3 - right 데이터가 없을 때

    while len(right) > right_point:

        merged.append(right[right_point])

        right_point += 1

   

    return merged

 

최종 코드

def merge(left, right):

    merged = list()

    left_point, right_point = 0, 0

   

    # case1 - left/right 둘다 있을때

    while len(left) > left_point and len(right) > right_point:

        if left[left_point] > right[right_point]:

            merged.append(right[right_point])

            right_point += 1

        else:

            merged.append(left[left_point])

            left_point += 1

 

    # case2 - left 데이터가 없을 때

    while len(left) > left_point:

        merged.append(left[left_point])

        left_point += 1

       

    # case3 - right 데이터가 없을 때

    while len(right) > right_point:

        merged.append(right[right_point])

        right_point += 1

   

    return merged

 

 

def mergesplit(data):

    if len(data) <= 1:

        return data

    medium = int(len(data) / 2)

    left = mergesplit(data[:medium])

    right = mergesplit(data[medium:])

    return merge(left, right)

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG