[C++] 스택(Stack)

스택(Stack)

스택

 

문제

 

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

4949번: 균형잡힌 세상

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

int main(void)
{
	while (1) {
		string s;
		getline(cin, s);
		if (s.length() == 1 && s[0] == '.')
			break;

		stack<char> st;
		bool flag = true;
		for (int i = 0; i < s.length(); i++) {
			if (s[i] == '(' || s[i] == '{' || s[i] == '[')
				st.push(s[i]);
			else if (s[i] == ']' || s[i] == '}' || s[i] == ')') {
				if (!st.empty() && (st.top() == '[') && (s[i] == ']'))
					st.pop();
				else if (!st.empty() && (st.top() == '{') && (s[i] == '}'))
					st.pop();
				else if (!st.empty() && (st.top() == '(') && (s[i] == ')'))
					st.pop();
				else {
					flag = false;
					break;
				}
			}
		}

		if (flag && st.empty())
			cout << "yes\n";
		else
			cout << "no\n";
	}
	return 0;
}

 

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

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

int main(void)
{
	int n;
	cin >> n;

	stack<int> st;
	string answer = "";
	int num = 0;

	while (n--) {
		int temp;
		cin >> temp;

		while (st.empty() || st.top() < temp) {
			st.push(++num);
			answer += "+\n";
		}

		if (st.top() == temp) {
			st.pop();
			answer += "-\n";
		}
		else {
			cout << "NO\n";
			return 0;
		}
	}

	cout << answer;
	return 0;
}

 

https://www.acmicpc.net/problem/1406

1406번: 에디터

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

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;

	stack<char> StackL, StackR;
	for (int i = 0; i < s.length(); i++)
		StackL.push(s[i]);

	int M;
	cin >> M;
	while (M--) {
		cin >> s;
		if (s == "L") {
			if (!StackL.empty()) {
				StackR.push(StackL.top());
				StackL.pop();
			}
		}
		else if (s == "D") {
			if (!StackR.empty()) {
				StackL.push(StackR.top());
				StackR.pop();
			}
		}
		else if (s == "B") {
			if (!StackL.empty())
				StackL.pop();
		}
		else if (s == "P") {
			char tmp;
			cin >> tmp;
			StackL.push(tmp);
		}
	}

	while (!StackL.empty()) {
		StackR.push(StackL.top());
		StackL.pop();
	}

	while (!StackR.empty()) {
		cout << StackR.top();
		StackR.pop();
	}
}

 

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

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

int main()
{
	int n;
	while (cin >> n && n) {
		vector<int> height(n + 1);
		for (int i = 0; i < n; i++)
			cin >> height[i];

		stack<int> st;
		long long answer = 0;
		for (int i = 0; i <= n; i++) {
			while (!st.empty() && height[i] < height[st.top()]) {
				int t = st.top();
				st.pop();

				int width = i - (st.empty() ? 0 : st.top() + 1);
				answer = max(answer, (long long)height[t] * width);
			}
			st.push(i);
		}
		cout << answer << "\n";
	}
}

 

https://leetcode.com/problems/maximal-rectangle/description/

LeetCode - The World's Leading Online Programming Learning Platform

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        if (matrix.empty())
            return 0;

        int answer = 0;
        int c = matrix[0].size();
        vector<int> h(c + 1, 0);

        for (auto &v : matrix)
        {
            for (int i = 0; i < c; ++i)
                h[i] = v[i] == '0' ? 0 : h[i] + 1;

            stack<int> st;
            for (int i = 0; i <= c;)
            {
                if (!st.empty() && h[i] < h[st.top()])
                {
                    int top = st.top();
                    st.pop();

				    int width = i - (st.empty() ? 0 : st.top() + 1);
                    answer = max(answer, h[top] * width);
                }
                else
                    st.push(i++);
            }
        }

        return answer;
    }
};

 

https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        int answer = 0;
        stack<int> st;

        for (int i = 0; i < height.size(); ++i)
        {
            while (!st.empty() && height[i] > height[st.top()])
            {
                int top = st.top();
                st.pop();

                if (st.empty())
                    break;

                int heightWater = min(height[i], height[st.top()]) - height[top];
                int width = i - (st.top() + 1);
                answer += heightWater * width;
            }

            st.push(i);
        }

        return answer;
    }
};

 

https://leetcode.com/problems/min-stack/description/

#include <stack>
using namespace std;

class MinStack {
public:
    stack<int> s;
    stack<int> minS;

    MinStack() {
    }

    void push(int val) {
        minS.push((s.empty() || minS.top() > val) ? val : minS.top());
        s.push(val);
    }

    void pop() {
        s.pop();
        minS.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return minS.top();
    }
};

 

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

#include <stack>
using namespace std;

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> s;
        while (root != nullptr || s.empty() == false) {
            while (root != nullptr) {
                s.push(root);
                root = root->left;
            }

            root = s.top();
            s.pop();

            k--;
            if (k == 0)
                return root->val;
            
            root = root->right;
        }

        return -1;
    }
};