문제 링크

<aside> 💡 자료 구조/분할 정복/세그먼트 트리/정렬

</aside>

Memory 233148KB Time 684ms Code Length 810B

def merge_and_count(arr1, arr2):
    merged = []
    count = 0
    i = j = 0

    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            count += len(arr1) - i
            j += 1

    merged.extend(arr1[i:])
    merged.extend(arr2[j:])

    return merged, count

def merge_sort_and_count(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, left_count = merge_sort_and_count(arr[:mid])
    right, right_count = merge_sort_and_count(arr[mid:])
    merged, merge_count = merge_and_count(left, right)

    return merged, left_count + right_count + merge_count

N = int(input())
arr = list(map(int,input().split()))
print(merge_sort_and_count(arr)[1])

이 코드는 병합 정렬 알고리즘을 이용해 주어진 배열을 정렬하고, 배열을 정렬하는 과정에서 발생하는 '역순' 쌍의 개수를 세는 코드이다.

첫 번째 함수인 'merge_and_count'는 두 개의 정렬된 배열 arr1과 arr2를 병합하고, 병합하는 과정에서 발생하는 '역순' 쌍의 개수를 세는 함수이다. '역순' 쌍이란 arr1의 어떤 원소가 arr2의 원소보다 큰 경우를 말한다.

두 번째 함수인 'merge_sort_and_count'는 주어진 배열을 반으로 나누고, 각각을 재귀적으로 정렬한 후 병합하는 함수이다. 이 함수는 병합하는 과정에서 'merge_and_count' 함수를 호출하여 '역순' 쌍의 개수를 구한다.

마지막으로, 사용자로부터 배열의 크기 N과 배열의 원소들을 입력받아 'merge_sort_and_count' 함수를 호출하고, 그 결과로 반환된 '역순' 쌍의 개수를 출력한다.