BOJ 1517 버블 소트

난이도 H

버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내느 문제

비슷한 문제로 삽입 정렬을 수행할 때 숫자들을 총 몇 번 옮기는지 계산하기

일반적인 버블소트는 O(N^2) 이기 때문에

문제 조건에서의 수행 시간을 만족하지 못함

이 문제를 풀기 위해선 O(N logN) 시간을 만족해야 함

O(N logN) sort + binary search, 팬윅 트리(바이너리 인덱스드 트리) 등을 이용하는 방법이 있지만

병합 정렬을 이용해서 문제 풀이가 가능

자세한 설명은 JM Book 762 페이지를 참고