테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 열 정렬정렬 정 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:permcycle#permutation_cycles|teflib.permcycle.permutation_cycles]]

{{tag>BOJ ps:problems:boj:골드_4}}