[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개이다.
  

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

💡 새롭게 알게 된 점

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

---