굳건하게

문제 : https://www.acmicpc.net/problem/4949

[알고리즘풀이]

()괄호를 위한 스택1과 []괄호를 위한 스택2 두 개를 이용해서 문제를 해결한다.

1. '(' 괄호를 만나면 스택1에 푸쉬한다.

2. ')' 괄호를 만나면 스택1을 팝한다. 이때, 스택1이 비어있다면 '(' 와 짝이 맞지 않으므로 "NO"를

또 스택2의 top이 스택1의 top보다 크다면 "NO"를 출력하고 종료한다. 아니라면, 계속 진행한다.

* 다음과 같은 경우 : ( [ ) ] 를 의미한다. 

3. 진행이 완료되었을 때, 스택1에 남아있는 '('가 있다면 "NO"를 출력, 아니라면 "YES"를 출력한다.

[]괄호도 마찬가지로 1,2,3 과정을 거친다.

[주의사항]

( [ ) ] 과 같은 예시도 ( ) 와 [ ] 가 짝이 맞지만, 균형이 무너져 안 되는 점을 주의해야 한다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	while(1){
		bool flag = false;
		string input;
		getline(cin, input);
		if (input == ".")
			return 0;
		stack<int> s1, s2;
		for (int i = 0; i < input.length(); i++) {
			if (input[i] == '(') {
				s1.push(i);
			}
			else if (input[i] == '[') {
				s2.push(i);
			}
			else if (input[i] == ')') {
				if (s1.empty()) {
					flag = true;
					break;
				}
				if (s2.empty()) {
					s1.pop();
					continue;
				}
				int c1 = s1.top();
				int c2 = s2.top();
				if (c1 < c2) {
					flag = true;
					break;
				}
				s1.pop();
			}
			else if (input[i] == ']') {
				if (s2.empty()) {
					flag = true;
					break;
				}
				if (s1.empty()) {
					s2.pop();
					continue;
				}
				int c1 = s1.top();
				int c2 = s2.top();
				if (c1 > c2) {
					flag = true;
					break;
				}
				s2.pop();
			}
		}
		 if (flag || !s1.empty() || !s2.empty())
			cout << "no\n";
		else
			cout << "yes\n";
	}
}

문제 : https://www.acmicpc.net/problem/9012

[알고리즘풀이]

자료 구조 책 스택 단원에 소개될 만큼 대표적인 스택을 사용하는 문제다.

'(' 를 Input으로 받으면 스택에 Push하고, ')' 를 Input으로 받으면 반대로 스택을 Pop한다.

이때, 스택이 비어있어 Pop을 진행하지 못하거나, 모든 Input이 끝나고 짝이 맞지 않아 스택에 '(' 이 남아있다면

"NO"를 출력하고 위의 두 가지 경우가 아니라면 "YES"를 출력한다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int ninput;
	cin >> ninput;
	for (int i = 0; i < ninput; i++) {
		stack<int> list;
		string input;
		cin >> input;
		int flag = 0;
		for (int j = 0; j < input.length(); j++) {
			if (input[j] == '(')
				list.push(j);
			if (input[j] == ')') {
				if (list.empty()) {
					cout << "NO\n";
					flag = 1;
					break;
				}
				else
					list.pop();
			}
		}
		if (list.empty() && flag == 0)
			cout << "YES\n";
		else if (!list.empty() && flag == 0)
			cout << "NO\n";
	}
}

문제 : https://www.acmicpc.net/problem/10773

[알고리즘풀이]

0이 입력으로 들어오면, 가장 최근에 들어온 입력을 삭제해줘야 되는 문제이다.

즉, LIFO( Last In First Out ) 형식의 자료 구조인 스택을 이용하는 문제이다.

0이 아닌 입력을 Stack에 Push하고 0이 들어오면 Stack을 Pop하면 된다.

#include<iostream>
#include<stack>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
	stack<int> s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		if (input == 0)
			s.pop();
		else
			s.push(input);
	}
	int answer = 0;
	while (!s.empty()) {
		answer += s.top();
		s.pop();
	}
	cout << answer;
}

문제 : https://www.acmicpc.net/problem/10828

[알고리즘풀이]

자료구조 스택을 선언하고, 입력에 맞춰서 명령을 실행하면 되는 문제입니다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	stack<int> s;
	int t;
	cin >> t;
	while (t--) {
		string input, input2;
		cin >> input;
		if (input == "push") {
			cin >> input2;
			s.push(stoi(input2));
			continue;
		}

		if (input == "pop") {
			if (s.empty()) {
				cout << "-1\n";
			}
			else{
				cout << s.top() << '\n';
				s.pop();
			}
		}
		else if (input == "size") {
			cout << s.size() << '\n';
		}
		else if (input == "empty") {
			if (s.empty())
				cout << "1\n";
			else
				cout << "0\n";
		}
		else if (input == "top") {
			if (s.empty()) {
				cout << "-1\n";
			}
			else
				cout << s.top() << '\n';
		}
		else {
			s.push((int)input[4]);
		}
	}
}