테페리넷

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

===== 풀이 =====
  * 기본적으로 [[ps:problems:boj:25577]]과 같은 문제이다. 정렬된 상태가 아니라 B로 바꾸어야 하는게 다른점인데, B가 정렬된 상태가 되도록 원소값들을 치환한 뒤에 똑같은 방식으로 풀면 된다. 시간복잡도는 O(n)
  * 문제는 메모리 제한이 64MB로 너무 작다는 것이다. N이 최대 1,000,000 씩인데, 쉽게 풀려면 입력을 포함해서 N길이의 리스트가 4~5개를 만들어야 하는데 이러면 cpython으로는 메모리 초과가 발생한다.
    * pypy로 제출하면 통과되기는 한다. 그리고 cpython으로 통과시키려면, list대신 array.array 를 이용해서 값들을 저장해주는 방법으로 메모리 사용량을 줄일수 있다. teflib의 permutation_cycles 함수는 각 사이클에 포함되는 원소들을 모두 구해주는데, 그냥 사이클의 개수만 구해주는 함수를 사용하는 것으로 메모리 사용량을 줄일수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13214. Swaps".

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

Tags: [permutation cycle]
"""

import array


def count_permutation_cycles(perm):
    visited = [False] * len(perm)
    ret = 0
    for i in range(len(perm)):
        if visited[i]:
            continue
        cur = i
        ret += 1
        while (cur := perm[cur]) != i:
            visited[cur] = True
    return ret


def main():
    N = int(input())
    A = array.array('i', (int(x) - 1 for x in input().split()))
    B = array.array('i', (int(x) - 1 for x in input().split()))

    pos = array.array('i', [-1] * N)
    for i, b_i in enumerate(B):
        pos[b_i] = i
    perm = array.array('i', (pos[a_i] for a_i in A))
    answer = N - count_permutation_cycles(perm)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

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