[Judge]逆ペアリングを求める

🎯 アルゴリズムの挑戦-逆ペアを求める

🤔 私の答え

📌 質問する

- 알고리즘 과제 > 역쌍구하기

📌 名前の日付

2020.03.29

📌 試行回数

1

💡 Code

def solution(nlist):
    def merge(left, right):
        global inversion
        merged_list = []
        while left and right:
            if right[0] < left[0]:
                inversion += len(left) # 오른쪽에서 옮길 때 왼쪽에 남아 있는 요소의 개수만큼 역쌍이 존재
                merged_list.append(right.pop(0))
            else:
                merged_list.append(left.pop(0))
        if left:
            merged_list += left
        elif right:
            merged_list += right
        return merged_list
 
    if len(nlist) == 1:
        return nlist
 
    mid = len(nlist) // 2
    left = solution(nlist[:mid])
    right = solution(nlist[mid:])
    return merge(left, right)
 
 
# 입력 및 실행
for _ in range(int(input())):
    num = int(input())
    nlist = list(map(int, input().split()))
    inversion = 0 	# 역쌍의 개수
    solution(nlist)
    print(inversion)

💡 トラブルシューティング方法

ペアを求める方法は以下の通りです.
-右から左に移動すると、左の残りの要素の数に等しい逆のペアが存在します.

したがって,最終求偶の過程(+分割征服)は一目瞭然である.붉은색으로 칠한 블록は左側のブロックもあり、右側のブロックが先に着きます.노란색으로 칠한 블록は当時左に残っていた街です.
従って、以下の例では、逆対の個数は1 + 1 + 1 = 3個である.

答えを間違える理由

-

💡 新知

- 역쌍 개수를 구하는 알고리즘을 새롭게 알게 되었다.