프로그래밍/HackerRank
[HackerRank][Python3] Merge Sort: Counting Inversions
snoopybox
2018. 7. 22. 23:42
Problem :
https://www.hackerrank.com/challenges/ctci-merge-sort/problem
My Solution :
#!/usr/bin/env python3 def countInversions(arr, left, right): count = 0 if right - left < 2: return count middle = (right + left) // 2 left_count = countInversions(arr, left, middle) right_count = countInversions(arr, middle, right) count += left_count + right_count merged = [] i, j = left, middle while i < middle and j < right: if arr[i] > arr[j]: merged.append(arr[j]) j += 1 count += middle - i else: merged.append(arr[i]) i += 1 if i == middle: merged += arr[j:right] else: merged += arr[i:middle] arr[left:right] = merged return count t = int(input()) for _ in range(t): n = int(input()) arr = list(map(int, input().rstrip().split())) result = countInversions(arr, 0, n) print(result)