[알고리즘 연습] 마지막으로 남는 카드

마지막으로 남는 카드

• 1~n순서로 쌓여있는 카드뭉치가 존재한다. (맨 앞이 1)
• 앞부터 제일 앞카드는 버리고, 그 다음카드는 제일 뒤로 옮긴다.
• 해당 과정을 반복한다.
• 제일 마지막에 남는 카드 1장의 숫자를 리턴해라.

---

풀이

from collections import deque

def deque_process(n):
    my_deque = deque([i for i in range(1, n + 1)])
    while(len(my_deque) != 1):
        my_deque.popleft()
        my_deque.rotate(-1)
    return my_deque[0]

• 가장 기본에 충실한 방법이다.
• 카드뭉치를 deque로 만들고, 이를 pop하고 rotate하기를 카드뭉치 사이즈가 1이 될 때까지 반복한다.
• 그리고 마지막에 남는 카드를 리턴한다.

def another_process(n):
    pow_val = 1
    while pow_val < n:
        pow_val *= 2
    return n*2 - pow_val # pow_val-2*(pow_val - n)

print("test start")
for i in range(1,1001):
    if (another_process(i) != deque_process(i)):
        print("wrong value!")
print("test end")

• 문제 자체는 쉽게 풀었지만 흥미로웠던 것은 이 부분이다.
• 기존 방식대로 구한 뒤 100까지 결과를 출력해보면서 그 속에 숨겨진 패턴을 찾아냈다.
• 그 패턴대로 코드를 작성하고, 1~1000까지의 숫자를 대입해 기존값과 동일한지 확인했다.
• 이러한 패턴을 찾을 수 있다면 훨씬 더 시간복잡도 측면에서 유리한 코드를 작성할 수 있다. (실제로 기존 코드와 달리 패턴을 적용한 코드는 시간복잡도가 O(logN) 으로 매우 효율적임을 알 수 있다.)