문제 19
C++ Deque
처음에 빈 덱 $D$가 있다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
push_front x: $D$의 앞에 정수 $x$를 추가한다.push_back x: $D$의 뒤에 정수 $x$를 추가한다.pop_front: $D$의 첫 번째 원소를 삭제한다.pop_back: $D$의 마지막 원소를 삭제한다.front: $D$의 첫 번째 원소를 출력한다.back: $D$의 마지막 원소를 출력한다.size: $D$의 크기를 출력한다.
pop_front, pop_back, front, back 쿼리는 항상 올바른 상태에서만 주어진다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
쿼리에 포함되는 정수 $x$의 범위는 다음과 같다. $(-10^9 \le x \le 10^9)$
출력
front, back, size 쿼리마다 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
10 push_back 3 push_front 1 front back size push_back 5 pop_front front pop_back back
예제 출력 1
1 3 2 3 3
공식 해설
양 끝에서 원소를 추가·삭제해야 하므로 덱을 사용한다. 스택이나 큐와 달리 앞과 뒤를 모두 직접 다룰 수 있는 자료구조이다.
front와 back에는 양 끝 원소를, size에는 남은 원소 수를 출력한다. 조회·삭제는 덱이 비어 있지 않을 때만 주어진다.
각 명령은 분할 상환 $O(1)$에 처리할 수 있으므로 전체 시간복잡도와 공간복잡도는 $O(Q)$이다.
구현 · 언어별 풀이
C++ 구현
deque<int>를 사용한다. 양 끝의 삽입은 push_front(x), push_back(x), 삭제는 pop_front(), pop_back()으로 처리한다. 양 끝 원소와 크기는 front(), back(), size()로 조회한다.
C 구현
$Q+1$칸의 원형 배열에 head와 길이를 둔다. 앞·뒤 인덱스를 나머지로 계산하고, 앞으로 이동할 때 head + capacity - 1을 사용해 음수 나머지를 피한다.
Python 구현
collections.deque의 appendleft(), append(), popleft(), pop()을 사용한다. 양 끝 조회는 d[0], d[-1]로 처리한다.
양 끝 연산의 대응은 다음과 같다.
from collections import deque
d = deque()
d.appendleft(x)
d.append(y)
front, back = d[0], d[-1]
d.popleft()
d.pop()Java 구현
ArrayDeque<Integer>의 addFirst(), addLast(), removeFirst(), removeLast()를 사용한다. peekFirst(), peekLast()로 양 끝을 조회한다.
앞쪽 연산과 뒤쪽 연산의 대응은 다음과 같다. 조회·삭제는 해당 원소가 있을 때 수행한다.
ArrayDeque<Integer> d = new ArrayDeque<>();
d.addFirst(x);
d.addLast(y);
int front = d.peekFirst();
int back = d.peekLast();
d.removeFirst();
d.removeLast();Rust 구현
VecDeque<i32>의 push_front(), push_back(), pop_front(), pop_back()을 사용한다. front()와 back()은 참조를 반환한다. 조회가 가능한 상태로 주어지므로 unwrap()으로 참조를 얻고 역참조하여 값을 읽는다.
use std::collections::VecDeque;
let mut d = VecDeque::<i32>::new();
d.push_front(x);
d.push_back(y);
let front = *d.front().unwrap();
let back = *d.back().unwrap();
d.pop_front();
d.pop_back();JavaScript 구현
최대 $Q$번 삽입되므로 길이 $2Q+1$의 Int32Array를 잡고 l=r=Q에서 시작하면 간단히 덱을 구현할 수 있다. 유효한 원소 구간을 $[l,r)$로 유지한다.
d[--l] = x; // push_front
d[r++] = x; // push_back
l++; // pop_front
r--; // pop_back
const front = d[l];
const back = d[r - 1];
const size = r - l;각 줄은 해당 명령에서만 실행한다. unshift()나 shift()로 원소 전체를 옮기지 않는다. 입력값 $\pm10^9$는 Int32Array 범위 안이며 모든 연산이 $O(1)$이다.