[백준] 21315번: 카드섞기(Python)

문제 

https://www.acmicpc.net/problem/21315

21315번: 카드 섞기

 

문제 풀이

- 분류: 완전탐색, 시뮬레이션

N, K의 크기가 크지 않아서 완전탐색 가능 ( 3중 for문을 돌려도 100 * 2 * 10 = 2000번 정도??.. 2^k < N 이므로 K 가 커봤자 9이다.)

- 두단계만 진행하므로 주어진 N에 따른 최대 크기의 K를 구해서 -> 중복조합을 이용해서 모든 k의 경우의 수를 구해주었다.

from itertools import product

max_k = int(math.log2(n))
candi = list(product(range(1, max_k + 1), range(1, max_k + 1))) #중복조합 리스트

 

- 중복 조합 리스트를 토대로 결과와 똑같이 나올때까지 반복해준다. 

- 그나마 del 이 짧게 걸리기 때문에 했음..

코드

import math
from copy import deepcopy
from itertools import product

n = int(input())
result = list(map(int, input().split()))
origin = [i for i in range(1, n+1)]
max_k = int(math.log2(n))
candi = list(product(range(1, max_k + 1), range(1, max_k + 1)))


for data in candi:
    cards = deepcopy(origin)
    for k in data:
        tmp = [] #직전에 올린 것 담기
        for i in range(1, k + 2):
            # 첫번째 단계
            if i == 1:
                tmp = cards[-2**k:]
                del cards[-2**k:]
                cards = tmp + cards
            else: #나머지 단계
                tmp = tmp[-2**(k-i+1):]
                cards = list(filter(lambda x: x not in tmp, cards))
                cards = tmp + cards
                
    if cards == result:
        print(' '.join(map(str,data)))
        break