스택 중간난이도 문제 풀이(Stack PS)

스택

가장 큰 특징 : 
LIFO
마지막에 넣은 게 가장 먼저 나온다

 

문제를 풀이하면서 가장 중요한 건

스택을 어떤 용도로 사용하고.
어떤 경우에 push를 하고, 
어떤 경우에 pop을 해야 할까? 를 생각해야 된다.

 

문제풀이
9935 문자열 폭팔 : https://www.acmicpc.net/problem/9935
가장 쉽게 생각하는 방법 :
배열에 문자를 저장해서 폭발이 없을 때까지 포문 돌리기
O(N*N), N = 백만이므로 불가능

stack 사용 -> 문자열이 폭파하였을 때, 폭파 가능한 이전 문자열을 O(1)만에 찾을 수 있다.
(서로 다른 문자 이므로 가능, 중복이 될 경우 첫 번째 문자인지 마지막 문자인지 구별이 안됨에 따라서 스택 알고리즘 적용이 어렵다.)

폭파 대상을 저장하는 stack

1. 폭파 문자열의 첫 대상일 경우 
push
2. 폭파문자열의 다음 대상일 경우 
push
2.1 폭파 문자열의 마지막 대상일경우 
폭파문자열 길이만큼 pop
3. 둘 다 아닐 경우 
stack all pop

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;

char str[1000001], boom[1000001];
bool erased[1000001];

int main(void) {
	scanf("%s %s", str, boom);
	int strLen = strlen(str);
	int boomLen = strlen(boom);
	stack<int> ans, tmp;

	if (boomLen == 1) {
		for (int i = 0; i < strLen; ++i) {
			if (str[i] == boom[0]) {
				erased[i] = true;
			}
		}
	}
	else {
		for (int i = 0; i < strLen; ++i) {
			ans.push(i);
			if (str[i] == boom[0]) {
				tmp.push(0);
			}
			else {
				if (!tmp.empty()) {
					if (str[i] == boom[tmp.top() + 1]) {
						tmp.push(tmp.top() + 1);
						if (str[i] == boom[boomLen - 1]) {
							for (int j = 0; j < boomLen; ++j) {
								int num = ans.top();
								erased[num] = true;
								ans.pop();
								tmp.pop();
							}
						}
					}
					else {
						while (!tmp.empty()) tmp.pop();
					}
				}
			}
		}
	}

	bool printed = false;
	for (int i = 0; i < strLen; ++i) {
		if (erased[i] == false) {
			printed = true;
			cout << str[i];
		}
	}
	if (printed == false) cout << "FRULA";

}

6549 히스토그램에서 가장 큰 직사각형 : https://www.acmicpc.net/problem/6549
가장 쉽게 생각 나는 풀이는 뭘까?
가능한 모든 직사각형의 크기를 구하면서 이동하기
크기 n 이므로 계속 1씩 커지는 모형이라고 할 때 직사각형 개수 : nx(n+1)/2, O(n^2), 10^10 이므로 불가능

여기서 중복을 줄일 수 있을까?
가정 1 : 앞으로 가면서 값이 증가할 때는 구할 필요가 없지 않을까? 값이 감소할 때만 크기를 구하기
확인 : 내림차순으로 정렬되어 있을 때는 불가능.

가정 2 : 각 높이에서 왼쪽 끝과 오른쪽 끝을 구해야 된다.
왼쪽 끝의 위치를 스택을 이용해서 구현해보자.

 

반례를 찾기 힘들어서 구글링 하였다.
http://www.informatik.uni-ulm.de/acm/Locals/2003/input/histogram.in

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	vector<int> v(100001, 0);
	stack<int> s;
	while (1) {
		long long max = 0;
		cin >> n;
		if (n == 0) 
			return 0;
		for (int i = 1; i <= n; ++i) {
			cin >> v[i];
		}
		s.push(1);
		for (int i = 2; i <= n; ++i) {
			if (v[s.top()] <= v[i]) {
				s.push(i);
			}
			else {
				int right = s.top();
				while (!s.empty()) {
					int now = s.top(), prev;
					if (v[s.top()] <= v[i]) 
						break;
					s.pop();
					if (s.empty()) 
						prev = 0;
					else 
						prev = s.top();
					if (max < (long long)v[now] * (right - prev))
						max = (long long)v[now] * (right - prev);
					//cout << "i : " << i << ", now : " << now << ", prev : " << prev << ", v[now] : " << v[now]<<", area : " << (long long)v[now] * (now - prev) << ", s.size() : " << s.size() << endl;
				}
				s.push(i);
			}
		}
		while (!s.empty()) {
			int now = s.top(), prev;
			s.pop();
			if (s.empty()) 
				prev = 0;
			else 
				prev = s.top();
			if (max < (long long)v[now] * (n - prev))
				max = (long long)v[now] * (n - prev);
		}
		cout << max << endl;
	}
}

3015 오아시스 재결합
스택을 어떤 용도로 사용하고.
어떤 경우에 push를 하고, 
어떤 경우에 pop을 해야 할까? 를 생각하자!!

많은 반례를 생각해야 했고, 답이 int범위를 넘어가는 것 주의

예제의 7, 2 4 1 2 2 5 1을 봤을 때
2(0번) 다음에 4(1번)가 있어서 이후에 있는 수들은 2를 보지 못한다.
스택에 볼 수 있는 가능성이 있는 것들을 넣어보자.

1. 다음 수가 왔을 때 스택 탑과 비교하자.
2.1 더 작을 경우
답 +1;
pop
2.2 같을 경우
답 + 스택 탑의 중복수 
다음수에 중복수를 추가
pop
2.3클경우
답 + 스택 탑의 중복수
스택 탑이 크거나 같을 때까지 pop 
3. 다음 수 push
 
생각했던 반례들 
7 2 4 1 2 2 5 1
5 1 2 3 4 5
5 5 4 3 2 1
4 1 2 2 1
4 2 1 1 2
7 5 4 3 2 2 1 2
8 1 2 1 3 1 2 1 2

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	long long n, ans = 0;
	cin >> n;
	vector<int> v(n);
	stack<pair<int, long long> > s;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}

	for (int i = 0; i < n; ++i) {
		pair<int, int> p = { v[i], 1 };
		while (!s.empty()) {
			if (s.top().first > p.first) {
				ans += 1;
				break;
			}else if (s.top().first == p.first) {
				ans += s.top().second;
				p.second = s.top().second + 1;
				s.pop();
			}else {
				ans += s.top().second;
				s.pop();
			}
		}
		s.push(p);
	}
	cout << ans;
}