재밌는 문제 백준 21315 카드섞기

문제

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

21315번: 카드 섞기

 

코드의 양이 적어서 그런지 구현문제중에서 몇 안되는 재밌는문제이다.(난 구현이 너무 싫다.)

생각할거리도 있다.

1. 1≤ K, 2^K < N

입력조건에 있다. 2^K는 1000보다 작다. K는 최대 9로 설정이 가능하다.(2^10 = 1024)

엄청나게 작은 숫자이므로 브루트포싱의 단서가 된다.

2^K가 들어가는 문제는 보통 비트,log와도 관련지어서 생각이 가능하긴 한데 일단 여기서 알 수 있는건 k는 무척이나 작은 수만 가능하다이다.

2. 어떻게 (2,K)섞기를 할까?

여기서 생각해볼건

1. (2,K)섞기는 무대뽀로 하기엔 무척이나 비효율적이지 않은가? N^2일거같은데...

무대뽀로 섞어도 된다.(섞기를 다구현해도된다.)

왜냐하면 K가 9이므로 N^2의 복잡도로 섞어도 가능할 것이고,(N도 작다.)

섞는 횟수의 총합은 2^K + 2^(K-1) + 2^(K-2) + ... + 2^1 + 2^0이다.

2의 거듭제곱의 합은 2^(K+1)이다. K는 최대9이므로 2^(K+1) <= 1024이다. (O(N)과 비슷하다!)

2. 어떻게 구현하지?

엄청나게 많은 방법이 있을 것이다.

나는 섞고, 섞은걸 또 섞고.... 재귀적으로 구현하였다.

2^K개를 섞어야하면, 앞에있는 N - (2^K)개의 카드는 밑으로 갈것이고, 다음단계에선 섞이지 않을 것이다.(영향받지않는다.)

따라서 다음단계에도 섞일 뒤에있는 2^K개의 카드와 다음단계와 무관한 앞의 N-2^K개의 카드를 분리한다.

N-2^K개의 카드를 뒤로 보낸다.

다음 재귀함수에서 2^K개의 카드를 넘겨준다. 이때 K는 1이 줄어든다.

재귀함수에서 리턴받은걸 앞에 붙혀준다.

그러다 K가 0이되면 남은카드수는 2개일 것이고, 이 둘을 서로 순서를 바꿔주면된다. 리턴해준다. 끝

 

def shuffle(a, k):
    if k == 0:
        return [a[1], a[0]] // 둘의 순서를 바꿔줌
    arr = list(a) // 복사
    result = deque([]) // 정답
    tmp = deque([]) // 임시
    for i in range(1 << k):
        tmp.appendleft(arr.pop()) // 뒤에있는 2^K개의 카드를 임시에 넣어줌
    while arr: // 앞에있는 N-2^K개의 카드
        result.appendleft(arr.pop()) // 맨 뒤에다 붙혀줌
    r = deque(shuffle(tmp, k - 1)) // 재귀
    while r: // 앞에다가 붙혀줌
        result.appendleft(r.pop())
    return list(result)

카드 섞는 코드를 제대로 구현했다면

(2,k1)섞기를 하고 (2,k2)섞기를 한 것을 1 <= k1 <= 최대K, 1 <= k2 <= 최대K에 대해 모두 다 해보면서 입력받은 배열과 섞기의 결과가 같다면 k1과 k2를 출력해준다.