[BOJ] Q10090 Counting Inversions

[BOJ] Q10090 Counting Inversions

Question

Language: Python

Difficulty: Platinum 5

해당 문제는 inversion couting을 활용한 문제로 2517과 동일한 방식으로 풀이가 가능하다.

Solution

def mergeSort(arr):
    length=len(arr)
    if length<=1:
        return arr

    mid=length//2

    left=mergeSort(arr[:mid])
    right=mergeSort(arr[mid:])
    
    return merge(left,right)

def merge(left,right):
    global answer
    i,j=0,0
    left_length=len(left)
    right_length=len(right)
    temp=[]
    while i < left_length and j < right_length:
        if left[i][0] < right[j][0]:
            temp.append(left[i])
            i+=1
        else:
            answer+=(left_length-i)
            temp.append(right[j])
            j+=1
    
    temp+=left[i:]
    temp+=right[j:]
    
    return temp
        
if __name__ == "__main__":
    n=int(input())
    numbers=list(map(int,file.readline().split()))
    answer=0
    mergseSort(numbers)
    print(answer)