문제

• https://www.acmicpc.net/problem/1091

아이디어

• 처음엔 S[i], i와 서로 교환 하는 줄 알았는데, 단순 배치였다.
• 카드를 섞을 때마다, 카드와 P를 비교해서 정답인지 체크한다.
• list를 copy할 때, list_A = list_B를 하면 단순히 객체만 복사하게 되므로 주의한다.

코드

N = int(input())

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

lst = [i for i in range(N)]
log = []

count = 0 

def ansCheck(P, lst):
    for i in range(N):
        if P[lst[i]] != i%3:
            return False

    return True

while count <= 200000:
    if ansCheck(P, lst) == True:
        break

    temp_lst = lst[:] # temp_lst = lst로 copy하면 lst 변경 시, temp_lst도 함께 변경된다

    for i in range(N):
        lst[S[i]] = temp_lst[i]

    count+=1

print(count if count <= 200000 else -1) 

리뷰

• 셔플의 최댓값을 몇번으로 잡아야 할 지 모르겠어서, 카드 배치를 누적해서 저장하고 같은 카드 배치가 나오면 끝내려고 했는데 아니었다. 왜 그런진 아직도 모르겠다..
• 그래서 N*N이면 충분하겠지 ! 라고 생각했지만 역시나 너무 작은 수 였고, 질문에 테스트케이스를 보면 10만정도 답이 나오는 경우가 있어서 20만으로 잡았다.
• 최댓값을 지정하고, 시간 복잡도를 계산하는게 정말 어려운 것 같다

GIT

• https://github.com/Kimjaeseop/acmicpc/blob/master/1091/1091.py