백준
[백준]2164번: 카드2(파이썬)
초코바나나쉐이크
2023. 6. 17. 23:56
https://www.acmicpc.net/problem/2164
2164번: 카드2
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가
www.acmicpc.net
num = int(input())
que = []
for i in range(num):
que.append(i+1)
while len(que)>1:
que.pop(0)
a = que.pop(0)
que.append(a)
print(que[0])맨 처음엔 단순히 pop을 사용하여서 구현하였다.
연속된 시간 초과로 멘탈이 나가버려서 구글의 도움을 받았다.
from collections import deque
num = int(input())
que = deque([i for i in range(1,num+1)])
while len(que)>1:
que.popleft()
move_num = que.popleft()
que.append(move_num)
print(que[0])찾아보니까 deque가 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다고 한다.
리스트의 양 끝 엘리먼트에 접근하여 삽입 또는 제거를 할 경우, 일반적인 경우에는 O(n)이 소요되는 데 반해, 덱(deque)는 O(1)로 접근이 가능하다고 한다.
시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 뺄 경우에는 대부분의 경우의 deque는 list보다 빠른 연산이 가능하다고 한다.
deque의 중요성과 시간복잡도의 중요성을 다시금 깨달을 수 있는 좋은 문제였다!