문제 10
C++ Vector
처음에 빈 벡터 $V$가 있다. 원소의 인덱스는 $0$부터 $\lvert V \rvert-1$까지이다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
push_back x: $V$의 뒤에 정수 $x$를 추가한다.pop_back: $V$의 마지막 원소를 삭제한다.front: $V$의 첫 번째 원소를 출력한다.back: $V$의 마지막 원소를 출력한다.get i: $V$의 $i$번째 원소를 출력한다.
pop_back, front, back, get 쿼리는 항상 올바른 상태에서만 주어진다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
쿼리에 포함되는 정수 $x$와 인덱스 $i$의 범위는 다음과 같다. $(-10^9 \le x \le 10^9; 0 \le i < \lvert V \rvert)$
출력
front, back, get 쿼리마다 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
10 push_back 3 push_back 7 front back get 1 pop_back back push_back 10 get 1 front
예제 출력 1
3 7 7 3 10 3
공식 해설
원소의 순서를 유지하면서 맨 뒤에서만 추가·삭제하고, 인덱스로 원소를 조회해야 한다. 이 연산들을 지원하는 동적 배열을 사용한다.
조회·삭제는 항상 가능한 상태에서 주어진다.
추가 한 번은 분할 상환 $O(1)$, 나머지 연산은 $O(1)$이므로 전체 시간복잡도는 $O(Q)$, 공간복잡도는 $O(Q)$이다.
구현 · 언어별 풀이
C++ 구현
빈 vector<int> v를 만든다. 추가와 삭제는 v.push_back(x), v.pop_back()으로 처리한다. 첫 원소, 마지막 원소, 인덱스 $i$의 원소는 각각 v.front(), v.back(), v[i]로 읽는다. 문제의 인덱스도 $0$부터 시작한다.
C 구현
추가 횟수가 $Q$ 이하이므로 int 배열 $Q$칸과 길이 변수만 둔다. 뒤에 추가하고 뒤에서 제거하며, 앞·뒤·인덱스 조회는 배열 접근으로 처리한다. 삭제할 때 배열을 이동하지 않는다.
Python 구현
list의 append(), pop(), 인덱싱과 len()을 사용한다. 뒤쪽 삭제는 pop()이며 앞 원소 조회는 a[0]이다.
Java 구현
ArrayList<Integer>의 add(), remove(size() - 1), get()을 사용한다. 인덱스 삭제와 값 삭제 오버로드를 혼동하지 않도록 마지막 인덱스를 전달한다.
ArrayList<Integer> a = new ArrayList<>();
a.add(x);
int last = a.get(a.size() - 1);
a.remove(a.size() - 1);Rust 구현
Vec<i32>의 push(), pop(), first(), last()와 인덱싱을 사용한다. 조회가 가능한 상태로 주어지므로 first()와 last()의 반환값을 unwrap()으로 얻을 수 있다.
JavaScript 구현
일반 Array가 동적 벡터에 해당한다. push(x), pop(), a[0], a[a.length - 1], a[i], a.length를 각각 필요한 명령에 연결한다. 입력값 $\pm10^9$는 Number로 정확하다.
답은 문자열 배열에 모아 한 번에 출력한다.