문제 16
C++ Stack
처음에 빈 스택 $S$가 있다. $Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
push x: $S$의 위에 정수 $x$를 추가한다.pop: $S$의 맨 위 원소를 삭제한다.top: $S$의 맨 위 원소를 출력한다.size: $S$의 크기를 출력한다.
pop, top 쿼리는 항상 올바른 상태에서만 주어진다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 100\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
쿼리에 포함되는 정수 $x$의 범위는 다음과 같다. $(-10^9 \le x \le 10^9)$
출력
top, size 쿼리마다 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
8 push 3 push 5 top size pop top push 7 top
예제 출력 1
5 2 3 7
공식 해설
가장 나중에 넣은 원소부터 제거하므로 후입선출 자료구조인 스택을 사용한다. 원소를 추가하면 맨 위에 놓고, 삭제하면 맨 위 하나만 제거한다.
top에는 맨 위 원소를, size에는 남은 원소 수를 출력한다. 조회·삭제는 스택이 비어 있지 않을 때만 주어진다.
각 명령은 분할 상환 $O(1)$에 처리할 수 있으므로 전체 시간복잡도와 공간복잡도는 $O(Q)$이다.
구현 · 언어별 풀이
C++ 구현
C++에서는 stack<int>의 push(x), pop(), top(), size()를 사용한다. pop()은 값을 반환하지 않으며, 문제에서도 삭제 명령에는 출력하지 않는다.
C 구현
$Q$칸의 배열과 길이 변수 top을 둔다. push는 a[top++]에 대입하고 pop은 top을 줄인다. 맨 위 원소는 a[top - 1]이다.
Python 구현
list를 스택으로 사용한다. append(), pop(), a[-1], len(a)가 필요한 연산에 대응한다.
Java 구현
ArrayDeque<Integer>의 addLast(), removeLast(), peekLast(), size()를 사용한다.
스택의 위쪽을 덱의 뒤쪽으로 정하면 아래 연산을 사용한다. 조회·삭제는 문제에서 허용하는 비어 있지 않은 상태에서 수행한다.
ArrayDeque<Integer> s = new ArrayDeque<>();
s.addLast(x);
int top = s.peekLast();
s.removeLast();Rust 구현
Vec<i32>의 push(), pop(), last(), len()을 사용한다. 조회가 가능한 상태로 주어지므로 맨 위 원소는 last().unwrap()으로 얻을 수 있다. pop()의 반환값은 출력하지 않는다.
JavaScript 구현
Array의 push(x)와 pop()으로 스택을 유지하고 맨 위는 s[s.length - 1], 크기는 s.length로 조회한다.