ALGORITHM NOTE1

BOJ 10828 - 스택

스택 연습하자 스택

#algorithm#boj#silver#data-structures#implementation#stack
아카이브로 돌아가기

문제 링크

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

  • push X: 정수 X를 스택에 넣는 연산이다.
  • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 스택에 들어있는 정수의 개수를 출력한다.
  • empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
  • top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

명령을 그대로 스택 연산으로 옮기면 되는 구현 문제다. 핵심은 push, pop, top, size, empty를 각각 정확하게 정의하고, 비어 있는 경우 예외 처리를 빠뜨리지 않는 것이다.

현재 코드는 직접 Stack 클래스를 만들고, 배열과 top 인덱스로 스택을 구현한다. push에서는 인덱스를 하나 올린 뒤 값을 넣고, pop에서는 비어 있는지 먼저 확인한 뒤 맨 위 값을 꺼내면서 크기를 줄인다.

표준 라이브러리를 쓰지 않고도 스택이 어떻게 동작하는지 드러나는 구현이라서, 자료구조의 기본 동작을 확인하기에 좋은 형태다.

코드

cpp
#include <iostream>
#define MAX_SIZE 10001
using namespace std;
 
class Stack {
private:
	int t, s;
	int* stack;
public:
	void init_Stack();
	void push(int x);
	int pop();
	int size();
	int empty();
	int top();
	Stack() { init_Stack(); }
};
 
void Stack::init_Stack() {
	s = 0;
	t = -1;
	stack = new int[MAX_SIZE];
}
 
void Stack::push(int x) {
	stack[++t] = x;
	s++;
}
 
int Stack::pop() {
	if (empty()) {
		return -1;
	}
	else {
		int temp = stack[t--];
		s--;
		return temp;
	}
}
 
int Stack::size() {
	return s;
}
 
int Stack::empty() {
	if (size() > 0)
		return 0;
	else
		return 1;
}
 
int Stack::top() {
	if (empty()) {
		return -1;
	}
	else {
		return stack[t];
	}
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int N = 0;
	cin >> N;
 
	Stack s;
 
	string order;
	for (int i = 0; i < N; i++) {
		cin >> order;
 
		if (order == "push") {
			int n;
			cin >> n;
			s.push(n);
		}
		else if (order == "pop") {
			cout << s.pop() << '\n';
		}
		else if (order == "size") {
			cout << s.size() << '\n';
		}
		else if (order == "empty") {
			cout << s.empty() << '\n';
		}
		else if (order == "top") {
			cout << s.top() << '\n';
		}
	}
 
	return 0;
}

복잡도

  • 시간 복잡도: 명령 NN개를 각각 상수 시간에 처리하므로 O(N)O(N)이다.
  • 공간 복잡도: 스택에 최대 NN개의 값이 들어갈 수 있으므로 O(N)O(N)이다.

마무리

배열과 top 인덱스만 있어도 스택 명령 다섯 가지는 그대로 구현된다.