[Hackerrank] [Hard] Merge Sort: Counting Inversions

https://www.hackerrank.com/challenges/ctci-merge-sort/problem

Merge Sort: Counting Inversions | HackerRank

풀이

• 예제처럼 bubble sort로 구현하면 timeout 발생
• merge sort로 구현해도 timeout 발생함
  • merge 부분에서 list의 append함수를 지역 변수로 사용하는게 빠름.
  • 필요한 정보들( len(list) 등)을 미리 변수에 할당하고 사용하는게 빠름.
• 가운데 index를 계산해 둘 씩 나누다가, 합칠 때 inversion 경우를 count함.
  • i < j 일 때, arr[i] < arr[j]라면 넘어가고, arr[i] > arr[j]일 때 계산
  • left_lst_len - i를 더해줌.
    • [1, 4, 7] / [3, 5, 8 ]을 sorted_lst에 merge하는 상황에서 오른쪽 리스트에서 3을 append하는 경우를 생각.
      • merge sort의 중간 과정이기 때문에 left_lst, right_lst는 항상 정렬되어 있음.
    • sorted_lst = [1] , i = 1(4에 대한 index), j = 0(3에 대한 index)
    • 예제처럼 인접한 원소끼리 값을 swap한다면, 2번을 해야 함.
      • [1, 4, 7, 3, 5, 8] -> [1, 4, 3, 7, 5, 8] -> [1, 3, 4, 7, 5, 8]
    • 하지만 swap 수를 바로 구할 수 있는데, left_lst의 전체 길이에서, sorted_lst에 들어간 원소 개수인 i를 빼주면 됨.
      • i는 왼쪽 리스트에서 값을 비교하기 위한 index 정보, sorted_lst에 들어간 원소 개수에 대한 정보를 의미함.
      • [4, 7] 이 되고, right_idx[0] = 3보다 큰 수가 2개가 되기 때문에 2번 값을 바꿔주면 답을 구할 수 있음.
      • j의 정보는 상관없는게, arr [ j ]보다 큰 수가 left_lst에서 몇 개 있는지만 확인하면 되기 때문.
      • (참고) left_lst [ i : ]의 길이를 구해도 되지만, timeout 발생함. len(left_lst[i : ])

def sortAndCountInversion(arr):
    count_inversion = merge_sort(arr)
    return count_inversion[1]

def merge_sort(lst):
    if len(lst) <= 1:
        return lst, 0

    n = len(lst)
    mid = n//2
    left_lst, l_cnt = merge_sort(lst[:mid])
    right_lst, r_cnt = merge_sort(lst[mid:])
    sorted_lst, cnt = merge(left_lst, right_lst)
    return sorted_lst, l_cnt + r_cnt + cnt

def merge(left_lst, right_lst):
    sorted_lst = []
    left_lst_len = len(left_lst)
    right_lst_len = len(right_lst)
    # 이렇게 안하면 timeout 발생. 
    lst_append = sorted_lst.append
    i, j = 0, 0
    cnt = 0
    while i < left_lst_len and j < right_lst_len:
        if left_lst[i] <= right_lst[j]:
            lst_append(left_lst[i])
            i += 1

        else:
            lst_append(right_lst[j])
            j += 1
            # len(left_lst[i:]) timeout 발생
            cnt += left_lst_len - i

    sorted_lst  += left_lst[i :]
    sorted_lst += right_lst[j:]
    return sorted_lst, cnt