https://www.acmicpc.net/problem/1517
이 문제는 N이 크므로 당연히 버블 소트를 직접 해서 푸는건 아니다. swap의 최대 횟수 역시 O(n^2)이므로 swap을 '하나씩' 세어서는 시간 안에 답을 낼 수 없다. 여러개의 swap을 한번에 카운팅하는 알고리즘이 필요하다.
즉 swap을 다른 방식으로 세어야 하므로 세는 관점을 한번 바꿔보자. 각각의 A[i]에 대해 A[i]가 다른 항과 몇번 swap되는지를 세는 것이다.
작은 N에 대해 예를 들어보면서 직접 이걸 세어보면, A[i]가 겪는 swap이 2종류가 있다는 것을 발견할 수 있다. A[i]가 왼쪽에서 오른쪽으로 가는 swap과 오른쪽에서 왼쪽으로 가는 swap 이렇게 2종류가 있다.
그래서 한번 경우를 나눠서 세어보려고 한다. 카운팅 문제에서 경우를 나눴더니 쉬워지는 것은 흔한 일이니까. 그런데 가만 생각해보니, 굳이 2종류의 swap 횟수를 모두 셀 필요가 없다! 하나의 swap에 대해 왼쪽 원소는 오른쪽으로 가고, 오른쪽 원소는 왼쪽으로 가기 때문에, 각각의 A[i]에 대해 "왼쪽에서 오른쪽으로 가는 swap"의 횟수만 세어줘도, 모든 swap이 한번씩 세어지게 된다. 이렇게 하면 swap이 중복해서 세어지는 일도 피할 수 있으니 일석이조이다.
따라서 "왼쪽에서 오른쪽으로 가는 swap"의 횟수(의 총합)만 빠르게 세면 되는데.. 이는 "A[i]보다 오른쪽에 있으면서 A[i]보다 작은 원소"들의 개수와 같음을 쉽게 알 수 있다. 왜냐하면 A가 정렬되기 위해서는 A[i]들이 이러한 원소들을 모두 한번씩 '뛰어넘어야' 하기 때문이다.
따라서 이러한 swap 횟수의 총합은 inversion의 개수와 같다. 따라서 구하고자 하는 답은 결국 inversion의 개수가 된다. 어려웠던 문제가 유명한 counting inversion 문제로 바뀐 것이다! counting inversion 문제는 O(nlogn)안에 풀 수 있으므로 어려움은 끝났다. 이제 여러분이 구현만 하면 된다.
(필자는 위의 증명(문제의 답이 inversion의 개수와 같다는 것에 대한 증명)이 누구나 쉽게 떠올릴 수 있는 증명이라고 생각합니다. swap의 횟수를 세는 관점을 바꾼다는 생각만 할 수 있으면 나머지 부분은 자연스럽게 따라나오니까요. 그러나 가장 짧고 우아한 증명은 아닐 수도 있습니다. 더 간결한 증명을 아시는 분은 댓글 남겨주시면 참고하도록 하겠습니다)