백준 21315. 카드 섞기

목차

1. 문제

2. 구현

3. 개선한 코드

---

2. 구현

가능한 k 조합을 2번 반복하더라도 시간 내에 풀 수 있으므로, 모든 조합을 생각했습니다.

 

1. 카드 섞기 함수를 제외한 나머지 코드를 완성

 - max_k 는 입력 카드 수 N 에 대해 나올 수 있는 최대 k

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
finish_list = list(map(int, input().split()))
start_list = [i for i in range(1, n+1)]

# max_k 구하기
max_k = 10
for i in range(max_k, 0, -1):
    if 2 ** i < n:
        max_k = i
        break

# 카드 섞기
def shake_cards(cards, cnt):
    # 나중에 해결
    pass

# 1부터 max_k까지 2가지를 뽑는 조합
for i in range(1, max_k + 1):
    for j in range(1, max_k +1):
        temp_list = shake_cards(start_list, i)
        temp_list = shake_cards(temp_list, j)

        if temp_list == finish_list:
            print(i, j)
            break

 

2. 관건은 카드를 섞는 로직인데, deque을 이용해서 해결했습니다.

 >> 덱을 2개를 만들어서, 분리해서 관리하는 게 핵심

2-1. 카드 섞기 전 카드 리스트에서 2의 제곱만큼 pop해서 q(카드 섞기 전 카드 리스트) 에 넣고

2-2. 나머지 만큼 pop 해서 result_q(카드 섞기 후 카드 리스트)에 넣어서 관리

 

마지막으로는 반드시 q에 1개가 남기 때문에 덱 2개를 더하여 리턴하면 완성입니다.

# 카드 섞기
def shake_cards(cards, cnt):
    q = deque(cards) # 카드 섞기 전 카드 리스트
    result_q = deque() # 카드 섞기 후 카드 리스트

    for i in range(cnt, -1, -1):
        power_two = 2 ** i
        cards_len = len(q)
        for _ in range(power_two):
            q.appendleft(q.pop())
        for _ in range(cards_len-power_two):
            result_q.appendleft(q.pop())

    return list(q) + list(result_q)

 

3. 개선한 코드

- math.log2를 이용해 max_k를 구하는 방식

- 플래그 이용해 이중 반복문 탈출

import math
import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
finish_list = list(map(int, input().split()))
start_list = [i for i in range(1, n+1)]

max_k = math.floor(math.log2(n-1)) # 최대 섞기 횟수(로그 계산)


# 카드 섞기
def shake_cards(cards, cnt):
    q = deque(cards) # 카드 섞기 전 카드 리스트
    result_q = deque() # 카드 섞기 후 카드 리스트

    for i in range(cnt, -1, -1):
        power_two = 2 ** i
        cards_len = len(q)
        for _ in range(power_two):
            q.appendleft(q.pop())
        for _ in range(cards_len-power_two):
            result_q.appendleft(q.pop())

    return list(q) + list(result_q)


found = False # 찾았는지 여부

for i in range(1, max_k + 1): # 1부터 max_k까지 2가지를 뽑는 조합
    if found:
        break
    for j in range(1, max_k +1):
        temp_list = shake_cards(start_list, i)
        temp_list = shake_cards(temp_list, j)

        if temp_list == finish_list:
            print(i, j)
            break