[BOJ] [Python] 백준 자료구조 Deque - 2164: 카드2

문제: 2164: Zero

• 백준 2164 자료구조
• Silver IV
• 문제링크

2164번: 카드2

첫 시도: 시간초과

1~N 까지의 수를 스택에 append 한다. for loop이 한번 돌 때 스택의 가장 위의 원소를 pop해주고 그 다음 원소의 인덱스를 재설정 해준다. 스택의 가장 밑에 위치하도록 원소의 인덱스를 재설정해주고 그에 따라 다른 원소들의 인덱스 역시 재설정 해준다.

스택의 가장 하위에 새로운 원소를 추가하는 것이 어려워 애초에 스택에 입력 값을 역순으로 넣어주었다.

lst = [1, 2, 3, 4] # lst.pop(0)-> x = lst[0].pop -> lst.append(lst[0])

N = int(input())
stack = []
for i in range(N):
    stack.append(i+1)           # 입력 역순으로 스택에 push 해주기
while len(stack) > 1:           # 스택이 비어있지 않을 때
    stack.pop(0)                # 가장 하위 인자 pop
    top = stack.pop(0)          # 그 다음 하위 인자를 변수에 저장 후
    stack.append(top)           # 스택의 가장 상위에 append 해준다.
print(stack[0])

 

이렇게 구현하여 제출했더니 시간초과 에러가 떴다..

찾아보니 이 문제는 deque를 사용해서 풀면 더 빨리 풀 수 있다고 한다..!!

deque는 '덱'이라고 하며 Double Ended Queue의 약자이다. 큐와 스택을 둘 다 만들 수 있는 자료구조인데, 양 끝단에서 모두 push, pop이 가능하다. 파이썬에서 collections모듈 안의 deque는 CPython으로 구성되어 있어서 속도면에서 훨씬 빠르다고 한다. 비효율적으로 인덱스를 호출해서 push pop하는 것보다 훨씬 효율적이다!

Deque를 사용한 시도:

from collections import deque 

N = int(input()) 
queue = deque() 
for i in range(N): 
    queue.append(i + 1) 
    
while len(queue) > 1: 
    queue.popleft() 
    queue.append(queue.popleft()) 
print(queue.pop())

로직은 비슷하지만 코드 작성적인면과 시간적인 면에서 훨씬 효율적이다!