Minimum Swaps 2

생각했던 것

어떤 방식으로 하든 어쨌든 정렬인 문제다. 정렬 중 가장 빠른 정렬은 역시 퀵 정렬이기 때문에 퀵 정렬을 구현해서 스왑할때마다 카운트를 해주자!

웃기고 있네

너무나 당연하게도 퀵 정렬은 최악의 경우에 O(n^2)의 시간복잡도를 보여준다. 따라서 퀵정렬은 항상 가장 적은 swap 수를 보장해주지 못한다. 차라리 합병정렬을 하면 몰라… 그래서 어떻게 할것인가?

직관적으로 가보자

첫번째 원소부터 순차적으로 검사해서 해당 인덱스 i에서의 값이 i+1이 아니라면 원래 그 값이 있어야 할 위치와 바꿔준다. 즉 수식으로 나타내면 arr[i] != i+1 이면 swap(arr[i], arr[arr[i] - 1]) 인 것이다.

결과

맞았다… 이렇게 직관적으로 풀 문제였는데 괜히 돌아가려다가 망했다. 돌아갈거면 잘 돌아갔어야 했는데… 더 공부해야겠다.