문제
BOJ 10828, 스택
핵심
- 입력의 크기가 104이라 대략 O(N2) 이하의 알고리즘을 사용한다.
- 단순히 스택 사용에 관한 문제다. STL, Collection 사용에 익숙해지자.
개선
코드
시간복잡도
C++
#include <iostream>
#include <stack>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
stack<int> s;
int n;
cin >> n;
while (n--) {
string cmd;
cin >> cmd;
if (cmd == "push") {
int x;
cin >> x;
s.push(x);
}
else if (cmd == "pop"){
if (s.empty())
cout << -1 << '\n';
else {
cout << s.top() << '\n';
s.pop();
}
}
else if (cmd == "size") {
cout << s.size() << '\n';
}
else if (cmd == "empty") {
if (s.empty())
cout << 1 << '\n';
else
cout << 0 << '\n';
}
else if (cmd == "top") {
if (s.empty())
cout << -1 << '\n';
else
cout << s.top() << '\n';
}
}
}
Java
import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Stack<Integer> s = new Stack<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if ("push".equals(cmd)) {
int x = Integer.parseInt(st.nextToken());
s.push(x);
} else if ("pop".equals(cmd)) {
if (s.isEmpty()) {
bw.write(-1 + "\n");
continue;
}
bw.write(s.pop() + "\n");
} else if ("size".equals(cmd)) {
bw.write(s.size() + "\n");
} else if ("empty".equals(cmd)) {
if (s.isEmpty()) {
bw.write(1 + "\n");
continue;
}
bw.write(0 + "\n");
} else if ("top".equals(cmd)) {
if (s.isEmpty()) {
bw.write(-1 + "\n");
continue;
}
bw.write(s.peek() + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
}