덱
백준 10866: 덱 해설- python
✏️ 문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ✏️ 풀이 파이썬의 collections.deque를 이용하였다. 사용법에 대한 내용은 여기에서 from collections import deque import sys n=int(sys.stdin.readline()) dq=deque() for _ in range(n): order=list(sys.stdin.readline().split()) if order[0]=='..
파이썬 collections deque 사용법과 응용
✏️ deque Stack이나 queue처럼 한 방향에서 삽입과 삭제가 일어나는게 아니라 양방향에서 삽입과 삭제가 일어나는 자료구조이다. 파이썬에서 list를 사용하는 것과 유사하지만 deque를 사용하는 이유는 시간복잡도 때문이다. 리스트에서 0번 인덱스를 삭제한다고 생각해보자. 이때 리스트 내부에서는 0번 인덱스를 제거하고 끝이 아니라 뒤에있는 원소들을 앞으로 하나씩 당겨주는 연산을 더 수행하게된다. 따라서 list의 삭제연산은 O(n)이 걸리는데 반면 deque의 삭제연산은 O(1)이다. 따라서 push, pop이 빈번한 알고리즘의 경우 list보다 deque를 사용하는 것이 효율적이다. ✏️ collections.deque 1. collections.deque.append(x) : deque의 맨..