[C++] 백준 10828번 스택

1. 문제이해

10828번: 스택 (acmicpc.net)

10828번: 스택

 

명령어의 개수(N)와 명령어들을 입력받고, 정수를 저장하는 스택 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

문제 그대로 스택을 구현하면 되는 문제이다.

이전에 큐와 덱을 구현한 적이 있었는데, 그와 거의 유사한 문제이다.

스택이란, 후입선출(Last In First Out—LIFO)특성을 가지는 자료구조로,

쉽게 말해, 일종의 바닥이 막힌 상자라고 보면 된다.

가장 먼저 들어간 정보가 가장 마지막에 나오며,

반대로 가장 나중에 들어간 정보가 가장 처음에 나오게 된다.

스택의 구조는 다음과 같다.

이미지 출처: https://www.programiz.com/dsa/stack

 

스택은 C++에 자동적으로 구현이 되어있다. (<stack>)

스택의 기본적인 함수들, 문제에서 요구하는 함수들은 다음과 같다.

 

1. stack <데이터타입> 이름; 형태로 선언해준다.

ex) stack <int> s;

 

2. s.push(element);

: 스택에 element(원소)를 추가한다. (가장 윗부분에 추가)

 

3. s.pop();

: 스택의 원소를 삭제한다.

(가장 위의 원소, 즉, 가장 마지막에 삽입된 원소를 삭제)

 

4. s.size();

: 스택의 사이즈를 반환한다.

 

5. s.empty();

: 스택이 비어있는지를 확인한다.

 

6. s.top();

: 스택의 가장 위에 있는 원소를 반환한다.

: 가장 위에 있는 원소는 가장 마지막에 삽입된 원소이다.

 

 

 

3. 소스코드

#include <iostream>
#include <stack>
using namespace std;

int main() {
	stack<int> s;      // 스택
	int N;             // 명령의 수
	string command;    // 명령어
	int num;           // push 연산 시, 스택에 넣을 정수
	int result = 0;    // 각 명령어의 결과값

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> command;

		// 1. push
		if (command == "push") {
			cin >> num;
			s.push(num);
		}

		// 2. pop
		//    스택이 비어있으면 -1을 출력, 그 외에는 top 값을 출력 후 pop
		else if (command == "pop") {
			if (s.size() == 0) {
				result = -1;
				cout << result << endl;
			}
			else {
				result = s.top();
				cout << result << endl;
				s.pop();
			}
		}

		// 3. size
		else if (command == "size") {
			cout << s.size() << endl;
		}

		// 4. empty
		//    size함수를 통해, size가 0이면 스택이 빈 것이므로 1, 아니면 0 출력     
		else if (command == "empty") {
			if (s.size() == 0) {
				result = 1;
				cout << result << endl;
			}
			else {
				result = 0;
				cout << result << endl;
			}
		}

		// 5. top
		//    스택이 비어있으면 -1을 출력, 그 외에는 top 값을 출력
		else if (command == "top") {
			if (s.size() == 0) {
				result = -1;
				cout << result << endl;
			}
			else {
				result = s.top();
				cout << result << endl;
			}
		}
	}

	return 0;
}

명령어의 개수(N)를 입력받은 후, N만큼 for문을 반복한다.

for문 안에는 문제에서 요구하는 스택의 함수들이 구현되어있으며,

명령어(command)가 무엇이냐에 따라 다른 작업을 수행한다.

 

1. push의 경우, 원소를 하나 더 입력받아 해당 원소를 스택에 삽입한다.

2. pop의 경우, 스택이 비어있으면 -1을 반환하고 그렇지 않으면 top값을 반환 후, pop 해준다.

3. size는 스택의 사이즈를 바로 출력해주었고,

4. empty는 size함수를 이용해, 스택이 비어있으면 1, 아니면 0을 출력하도록 했다.

5. top 또한 스택이 비어있으면 -1을 출력하고, 그렇지 않으면 top값을 출력했다.

 

 

---

큐와 덱은 동일한 문제를 푼 적이 있는데 정작 스택은 푼적이 없었다는 걸 깨달았다..😱

스택이 제일 기본적인데 왜 큐와 덱을 먼저 할 생각을 했을까..?

풀이방법은 큐와 덱이랑 거의 동일해서 구현이 어렵지 않았던 문제였다.

 

큐와 덱 관련 동일한 문제는 아래 포스팅을 참고하자!🤗

 

<큐>

https://beginnerdeveloper-lit.tistory.com/35

[C++] 백준 10845번 큐

 

 

<스택>

https://beginnerdeveloper-lit.tistory.com/49

[C++] 백준 10866번 덱