큐 vs 덱 (백준 2164) (feat. 요세푸스 문제)

백준 2164번: 카드 2

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

 

본 문제를 처음 봤을 때 두 가지로 접근 방향을 생각했다.

• 적절한 자료구조 이용
• 수학적인 알고리즘 이용

문제의 제한시간이 중요한 조건일 것 같아서, 우선 list로 queue를 만들어 보고 안 되면 수학적인 방법을 쓰는 걸로 생각했다.

N = int(input())
lst = list((range(1, N+1)))
status = True
while(len(lst)>1):
    if status:
        lst.pop(0)
    else:
        lst.append(lst[0])
        lst.pop(0)
    status = not status
print(lst[0])

 

시간 에러가 났다. pop(0)을 하는 것은 첫 원소를 지우고, 나머지 원소를 하나씩 모두 옮기는 연산이 들어가야 해서 pop()보다 시간이 오래 걸릴 가능성이 있기 때문에 처음에 큐를 뒤집어서 받고 pop()을 사용하는 방법도 시도해 보았으나, 마찬가지로 시간 에러가 났다.

 

따라서, 양쪽에서 데이터를 넣고 뺄 수 있는 덱(deque)을 이용하기로 했다. 파이썬 내장 컨테이너 자료형(set, tuple, list, dict)은 시간 효율이 좋지 못하거나 기능이 제한된 경우가 있는데, collections라는 모듈에서는 이를 보완한 각종 자료구조를 제공한다. 어떤 자료구조가 있는지는 documentation(https://docs.python.org/ko/3/library/collections.html)을 참고해 보자.

from collections import deque
N = int(input())
lst = deque((range(1, N+1)))
while(len(lst)>1):
    lst.popleft()
    lst.append(lst.popleft())
print(lst[0])

 

이렇게 풀면 정답이 된다!!

 

요세푸스 문제

이 문제는 수학적인 알고리즘으로도 해결할 수도 있다. 원형으로 구성된 n명의 사람에서, 1번부터 수를 세어 k번째 사람을 제외하여 가장 마지막에 남는 사람을 찾는 형태의 문제를 요세푸스 문제(Josephus Problem)라고 한다.

 

이 문제에서 아이디어는 카드의 수가 2^N이라면, 마지막에 남는 카드는 반드시 2^N이라는 데 있다. 임의의 자연수는 2^N + a로 나타낼 수 있으므로, a개의 수를 제거한 뒤 마지막 수를 반환하면 된다. 이때 a개의 수는 1, 3, 5, 7, 9, ..., 2a-1가 제거될 것이므로, 마지막 수는 2a가 된다. 단, a=0이면 입력받은 수가 2의 거듭제곱이라는 의미이므로 그냥 N을 그대로 출력하면 된다. 이를 코드로 아래와 같이 작성할 수 있다.

import math
N = int(input())
lst = list(range(1, N+1))
a = N-2**int(math.log2(N))
print(2*(a) if a else N)