열 정렬정렬 정

• 중복값이 없는 수열을 정렬시키기 위한 최소 스왑 연산 횟수는 N - {순열사이클의 개수}이다 (정렬 (Sorting) 참고)
• 수열을 좌표압축을 통해 순열로 변환하는데에 O(nlogn), 순열 사이클의 개수를 세는것은 O(n). 총 시간복잡도 O(nlogn)

"""Solution code for "BOJ 25577. 열 정렬정렬 정".

- Problem link: https://www.acmicpc.net/problem/25577
- Solution link: http://www.teferi.net/ps/problems/boj/25577

Tags: [permutation cycle]
"""

from teflib import permcycle


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    compress_map = {x: i for i, x in enumerate(sorted(A))}
    perm = [compress_map[x] for x in A]
    answer = N - len(permcycle.permutation_cycles(perm))
    
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.permcycle.permutation_cycles