파이썬 알고리즘 210번 | [백준 1091번] 카드 섞기 - 구현

210. 카드섞기

1) 어떤 전략(알고리즘)으로 해결?

• 구현

2) 코딩 설명

<내 풀이>

import sys
# N개의 카드를 이용
n = int(sys.stdin.readline().strip())

# 각 카드가 어떤 플레이어에게 가야하는지 정보
p = list(map(int,sys.stdin.readline().strip().split()))

# target라는 곳에 각 사용자들이 (0,1,2) 받아야하는 카드 정보 기록
# 결국 target 이라는 배열과 똑같아야지, 우리가 찾고자 한 것을 찾아야 함 
target=[[] for _ in range(3)]
for k in range(n) :
    target[p[k]].append(k)

# 카드 순서 결정해주는 s 배열
s = list(map(int,sys.stdin.readline().strip().split()))

# 카드 담기 0부터 n-1까지의 카드
# 현재 카드 순서대로 담는 배열
card_seq=[]
for i in range(n) :
    card_seq.append(i) 

initcard = card_seq.copy()  

# 처음엔 0,1,2,3,4..n-1 로 배열, 
# 이 초기 순서 저장
# (-1 식별에 필요)

# 카드 섞 횟수
cnt = 0

while True :
    # cmp_with target 은 카드 섞은 뒤, 각 0,1,2 에게 
    # 할당해준 아이 - target이랑 비교할 아이지
    cmp_with_target=[[] for _ in range(3)]

    # 각 사람에게 배치해주기
    for j in range(n) :
        cmp_with_target[j%3].append(card_seq[j])

    # 이걸 해줬어야해, 
    for v in range(3) :
        cmp_with_target[v].sort()

    # 만약 똑같으면 카드 섞다가 우리가 찾고자 하는 target 찾은 것이지
    if cmp_with_target==target: print(cnt) ; exit()

    else : 
        cnt+=1
        tmps = card_seq.copy()
        for c in range(n) : 
            card_seq[s[c]] = tmps[c]
            # i번째 위치에 있던 카드는 S[i]번째 위치로 이동

        if card_seq==initcard:
            print(-1); exit()
            

<내 틀렸던 풀이, 문제점>

(1) 1차 난관

• okay 가능한 경우들은 다 해결됨, 근데 안되는 경우들은 언제지?,,,

import sys
# N개의 카드를 이용
n = int(sys.stdin.readline().strip())

# 각 카드가 어떤 플레이어에게 가야하는지 정보
p = list(map(int,sys.stdin.readline().strip().split()))

# pp라는 곳에 각 사용자들이 (0,1,2) 받아야하는 카드 정보 기록
pp=[[] for _ in range(3)]
for k in range(n) :
    pp[p[k]].append(k)

s = list(map(int,sys.stdin.readline().strip().split()))

# 카드 담기 0부터 n-1까지의 카드
ss=[]
for i in range(n) :
    ss.append(i) 

# 카드 섞섞 횟수
cnt = 0

while True :
    sss=[[] for _ in range(3)]
    for j in range(n) :
        sss[j%3].append(ss[j])

    for ssss in range(3) :
        sss[ssss].sort()

    if sss==pp: print(cnt) ; exit()
    else : 
        cnt+=1
        tmps = ss.copy()
        for c in range(n) : 
            ss[s[c]] = tmps[c]
            # i번째 위치에 있던 카드는 S[i]번째 위치로 이동
        print(ss)

-1의 조건 :

• 계속해서 카드를 섞어주다가 첫 순서 (initcard)랑 똑같은 거 발견했다면 , 한번 쭉 돌았는데도 못 찾은거니 찾을 수 없는 것 => 이 때 -1 !

<반성 점>

<배운 점>