데굴데굴

2164번: 카드2 (acmicpc.net) 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 입력이 50만까지 주어지기 때문에 시간 초과에 유의하여 풀어야 한다. 처음에는 리스트로 해결했는데 답은 맞았지만 시간 초과가 발생하여 deque 라이브러리로 해결했다. 아래 페이지를 보면 deque의 삽입/삭제 연산 시간 복잡도는 O(1), 리스트는 O(n)이라 설명하고 있다. 리스트는 삽입/삭제 연산에서 비워진 곳을 메우기 위해, 혹은 새로 삽입된 값의 자리를 만들어 주기 위해 원소가 추가로 이동하지만 deque는 ..

디큐 Dequeue / deque dequeue는 Stack과 Queue를 합친 자료구조로, 왼쪽과 오른쪽에서의 삽입과 삭제가 모두 가능하다. 파이썬에는 collections 모듈에 deque 클래스로 구현되어 있다. from collections import deque 오른쪽에 값 넣을 때 = append / 왼쪽에 값 넣을 때 = appendleft 가장 오른쪽 값을 삭제할 때 = pop / 가장 왼쪽 값 삭제할 때 = popleft 디큐 활용 예: Palindrome 문자열 s와 s를 거꾸로 뒤집은 문자열이 서로 같다면 Palindrome ex) 기러기, salsa, 다시합창합시다 (디큐를 쓰지 않고도 Palindrome 판별 코드를 작성할 수 있음.) 디큐를 쓰지 않은 코드 s = input('단..