문제

BOJ 10828, 스택

핵심

• 입력의 크기가 $10^4$이라 대략 $O(N^2)$ 이하의 알고리즘을 사용한다.
• 단순히 스택 사용에 관한 문제다. STL, Collection 사용에 익숙해지자.

개선

코드

시간복잡도

• $O(N)$

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();
    }
}