문제

카드 N장이 있다. 각 카드는 플레이어 0, 1, 2 중 한 사람에게 나눠줘야 한다. 카드를 섞는 방법 S가 주어진다. 카드를 섞을 때마다 i번째 위치에 있던 카드가 S[i] 위치로 이동한다.

목표는 카드를 정확히 나눠주는 것이다. 최소 몇 번 섞어야 하는지 구하는 프로그램을 작성하시오.

풀이

시뮬레이션 문제이다. 카드를 섞다가 원래 상태로 돌아오면 불가능한 것이다.

코드

N = int(input())

P = list(map(int, input().split()))
S = list(map(int, input().split()))

def shuffle_card(cards, S):
    new_cards = [0] * (N)
    for i, n_i in enumerate(S):
        new_cards[n_i] = cards[i]
    return new_cards

cards = P[:]
answer = [0, 1, 2] * (N // 3)
cnt = 0

while answer != cards:
    cards = shuffle_card(cards, S)
    cnt += 1

    if cards == P:
        print(-1)
        break

else:
    print(cnt)

시간 복잡도

O(N^2)