[백준_python] 카드 2 || 2164 (스택, 큐, 덱)

www.acmicpc.net/problem/2164

2164번: 카드2

스택(Stack)

후입 선출(LIFO : Last-In First-Out)

: 상자가 차례로 쌓인다고 생각
: 가장 최근에 쌓인 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다.

큐(Queue)

선입 선출(FIFO : First-In First-Out)

: 매표소라고 생각
: 가장 먼저 들어온 사람이 가장 먼저 나가게 된다.

덱(Deque)

double-ended queue
: 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

---

가장 먼저 들어간 값이 삭제되어야 하고, 가장 먼저 들어간 값이 다시 마지막으로 들어가 주어야 하는 문제
→ 선입 선출
즉, 큐에 해당하는 문제이다.

#카드 2
#? 시간 초과 아무래도 덱을 사용해야 하나 보다.
from queue import Queue

n = int(input())
que = Queue()
for i in range(n):
    que.put(i+1)

while (que.qsize()>1):
    que.get()
    que.put(que.get())

print(que.get())

일단 먼저, 큐는 데이터가 많아질 수록 느려진다고, 보통 덱을 많이 쓴다는 말에 그래도 일단 큐로 풀어보자! 했다
그래서 큐를 이용하였다. 모듈을 사용하지 않고 list로도 해줄 수 있지만, 모듈을 한 번 써먹어보고 싶었음..
(list로 해주는 경우에는 append와 pop(0)을 이용해주면 된다.)
 
그렇지만 역시나 시간 초과가 되었다. 
따라서 덱을 이용해주었다.!

#카드 2_2
from collections import deque

n = int(input())
deq = deque()
for i in range(n):
    deq.append(i+1)

while (len(deq)>1):
    deq.popleft()
    deq.append(deq.popleft())

print(deq.pop())

큐와 덱으로 짜여진 코드는 정말 똑같지만, 내부의 시간복잡도에서 덱이 큐보다 더 적게 걸리는 것 같다.