스택 문제풀이

내 스택에 관한 글 를 읽거나, 스택에 대한 지식이 있어야 풀이를 이해할 수 있다.

괄호의 값: https://www.acmicpc.net/problem/2504

풀이: 스택을 이용해서 현재 쌍을 만들어야 하는 괄호들을 나온 순서대로 저장해주는 것이 풀이의 핵심이다. 괄호 스택을 비우고 닫힐 때 추가되는 점수를 1로 해 준 뒤, 문자열을 순서대로 보면서 여는 괄호가 들어오면 스택에 넣고, 현재 닫힐 때 추가되는 점수에 괄호의 값을 곱해준다. 닫는 괄호가 들어오면, 괄호가 스택 맨 위의 괄호와 맞는지 확인해 준 후 맞지 않으면 0을 출력해 준 뒤, 스택 맨 위 괄호와 이웃해 있으면 닫힐 때 추가되는 점수를 정답에 더해 준 후, 스택에서 pop을 하고, 닫힐 때 추가되는 점수에 괄호의 값을 나눠주면 된다. 맨 마지막에는 스택이 비어있어야 올바른 괄호 문자열이라는 점에 주의해야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stack>
using namespace std;
int N, M, V;
stack<char>t;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin >> s;
	int i;
	t.push('.');
	int w = 1;
	int ans = 0;
	for (i = 0; i < s.size(); i++)
	{
		if (s[i] == '(' || s[i] == '[')
		{
			t.push(s[i]);
			if (s[i] == '(')
				w *= 2;
			else
				w *= 3;
		}
		else if (s[i] == ')')
		{
			auto a = t.top();
			t.pop();
			if (a != '(')
			{
				cout << 0;
				return 0;
			}
			if (s[i - 1] == '(')
				ans += w;
			w /= 2;
		}
		else
		{
			auto a = t.top();
			t.pop();
			if (a != '[')
			{
				cout << 0;
				return 0;
			}
			if (s[i - 1] == '[')
				ans += w;
			w /= 3;
		}
	}
	if (t.size() != 1)
		cout << 0;
	else
	{
		cout << ans;
	}
}

탑: https://www.acmicpc.net/problem/2493

스택에 현재 탑에서 보이는 탑들을 위치 순서대로 관리하면, 수신하는 탑을 찾을 수 있다. 현재 i번째 탑을 체크하고 있다고 하자. 스택 맨 위부터 둘러보면서 i번째 탑보다 낮은 탑이 있는지 확인하고, 있다면 그 탑을 스택에서 뺀다. 그런 다음에 스택이 비어 있으면 수신이 안 되는 것이고, 스택에 원소가 있으면 가장 위쪽의 원소가 수신하는 것이다. 이를 확인했으면 이제 i번째 탑을 보이는 탑에 넣으면 된다.

#include <iostream>
#include <stack>
using namespace std;
stack<int>s;
int arr[500100];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N,i;
	cin >> N;
	for (i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		arr[i] = a;
		while (!s.empty())
		{
			if (a <= arr[s.top()])
			{
				cout << s.top()+1 << ' ';
				break;
			}
			else
			{
				s.pop();
			}
		}
		if (s.empty())
		{
			cout << 0 << ' ';
		}
		s.push(i);
	}
}

히스토그램:https://www.acmicpc.net/problem/1725

특정 막대기에서 왼쪽이나 오른쪽으로 뻗어나갈 수 있는 범위를 알면, 정답을 구할 수 있다. 정답을 구하기 위해, 막대기들을 높이의 오름차순으로 넣어 두는 스택을 만들자. 배열을 순회하면서, 스택의 원소 중 높이가 자신보다 큰 것을 빼되, 정답을 (현재 위치-뺀 원소 다음 스택 원소-1==뺀 원소를 중심으로 만든 직사각형의 너비)* 뺀 원소의 높이와 원래 정답의 최댓값으로 바꿔준다. 높이가 0인 가상의 마지막 원소를 만들어서 그 원소도 순회하면, 모든 경우를 따지게 되고, 정답이 구해진다.

#include <iostream>
#include <stack>
using namespace std;
stack<int>way;
int N;
int histo[1000000];
int ans, minn;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int i;
	for (i = 0; i < N; i++)
	{
		cin >> histo[i];
	}
	for (i = 0; i < N; i++)
	{
		while (way.size() && histo[way.top()] > histo[i])
		{
			int height = histo[way.top()];
			way.pop();
			int width = i;
			if (way.size())
			{
				width = i - way.top() - 1;
			}
			ans = ans > width * height ? ans : width * height;
		}
		way.push(i);
	}
	while (way.size())
	{
		int height = histo[way.top()];
		way.pop();
		int width = N;
		if (way.size())
		{
			width = N - way.top() - 1;
		}
		ans = ans > width * height ? ans : width * height;
	}
	cout << ans;
	return 0;
}