알고리즘/[python] 백준 BOJ
[Python] Codility ArrayInversionCount
Alan_Kim
2025. 4. 15. 13:38
728x90
반응형
An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
당연히 하나씩 비교했을 시 O($N^{2}$)이 되므로 이를 개선할 필요성이 있다.
이 때 보통 병합정렬(merge sort)을 사용한다.
병합정렬은 분할(divide), 정복(conquer), 결합(combine) 3가지 step으로 문제를 해결하는 것이다.
def solution(A):
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr)//2
left, inv_left = merge_sort(arr[:mid])
right, inv_right = merge_sort(arr[mid:])
merged, inv_split = merge_and_count(left, right)
total_inversions = inv_left + inv_right + inv_split
if total_inversions > 1000000000:
return merged, -1
return merged, total_inversions
def merge_and_count(left, right):
merged = []
i = j = inversions = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
inversions += len(left) - i # Left[i:]는 전부 right[j]보다 크닌까 inversion 발생
j += 1
merged += left[i:]
merged += right[j:]
return merged, inversions
_, count = merge_sort(A)
return count if count != -1 else -1
728x90
반응형