기록방

👉 문제링크 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열을 버블 소트로 정렬했을 때, swap이 총 몇 번 발생하는지 출력한다. 🔸 문제 풀이 🔸 N이 50만까지 가므로 O(nlogn)의 알고리즘을 사용해야 한다. 여기서는 병합 정렬(Merge Sort)을 사용한다. 버블 소트는 1칸씩 이동할 수 있으므로, 정렬 후 바뀐 인덱스의 크기를 모두 더하면 된다. 병합 정렬에서 기존 인덱스보다 앞 인덱스로 옮길 때, 그 크기를 누적해서 출력한다...