BOJ 1517 버블 소트

BOJ 1517 버블 소트

https://www.acmicpc.net/problem/1517

https://github.com/simjaemun2/BaekJoon/blob/573ed75b9d62e5d0b6131fbb55f5fa6790eff75f/BOJ1517/BOJ1517.cpp

난이도 H

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

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

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

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

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

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

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

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