[0x08] 스택의 활용

연습문제 : BOJ 10799 [쇠막대기], BOK 2504 [괄호의 값]

 

- 10799 : 쇠막대기. 45분 못풀고 해답 봤음

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

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	stack<char> pipes;

	string	str;
	size_t	str_len = 0;
	size_t	answer = 0;

	cin >> str;
	str_len = str.length();

	for (int i = 0; i < str_len; ++i)
	{
		if (str[i] == '(')
		{
			pipes.push(str[i]);
		}
		else
		{
			pipes.pop();

			if (str[i-1] == '(')
			{
				answer += pipes.size();
				// 레이저 컷팅
			}
			else
			{
				answer += 1;
				// 파이프의 끝. 한번 잘린거나 다름없어서 한개 추가해줌
			}
		}
	}

	cout << answer;

	return 0;
}

 

연습 문제

 

2493: 탑

#include <iostream>
#include <stack>

#define X first
#define Y second

using namespace std;

int N;
stack<pair<int, int>> tower;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	tower.push({ 100000001, 0 }); // 넘을 수 없는 최대치의 벽 미리 삽입
	for (int i = 1; i <= N; i++) { // 인덱스 출력을 위해 1부터 시작
		int height;
		cin >> height;
		while (tower.top().X < height) // 더 높은 이전타워 탐색
			tower.pop();
		cout << tower.top().Y << " "; // 더 높은 타워의 레이저 송수신 결과
		tower.push({ height, i }); // 현재 타워 스택에 추가
	}
}

 

바킹독님의 소스. 나중에 다시 리벤지 하는걸로

핵심은 스택에 맨 먼저 넘을수 없는 최대높이, 인덱스 0의 값을 준다

 

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n;
	vector<int> towers;
	vector<int> temp_towers;
	vector<int> answer;

	cin >> n;

	int data;
	for (int i = 0; i < n; ++i)
	{
		cin >> data;
		towers.push_back(data);
	}

	int count = 0;

	while (true)
	{
		int tower = towers.back();
		towers.pop_back();

		temp_towers.push_back(tower);

		//count += 1;

		if (towers.empty())
		{
			break;
		}

		while (!temp_towers.empty() && temp_towers.back() < towers.back())
		{
			answer.push_back(towers.size());
			temp_towers.pop_back();
		}

		
	}

	while (!temp_towers.empty())
	{
		answer.push_back(0);
		temp_towers.pop_back();
	}

	for (int i = 0; i < n; ++i)
	{
		cout << answer.back() << " ";
		answer.pop_back();
	}

	return 0;
}

 

내가 원래 작성하던 코드

 

6198: 옥상 정원 꾸미기

#include <iostream>
#include <stack>

using namespace std;

#define MAXIMUM 1000000000

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	stack<pair<int, int>> building;
	int n;
	long long answer = 0;

	cin >> n;

	building.push({MAXIMUM + 1, 0});

	for (int i = 1; i <= n; ++i)
	{
		int h;
		cin >> h;

		if (h < building.top().first)
		{
			building.push({h, i});
		}
		else
		{
			while (h >= building.top().first)
			{
				answer += i - building.top().second - 1;
				building.pop();
			}
			building.push({ h, i });
		}

		// 남은 빌딩에 대한 처리
		if (i == n)
		{
			while (MAXIMUM >= building.top().first)
			{
				answer += i - building.top().second;
				building.pop();
			}
			break;
		}
	}

	cout << answer;

	return 0;
}

 

바로 위 탑의 개념을 활용함.

 

17298: 오큰수

#include <bits/stdc++.h>
using namespace std;

int a[1000000];
int ans[1000000];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  stack<int> S;
  for (int i = n - 1; i >= 0; i--) {
    while (!S.empty() && S.top() <= a[i]) S.pop(); // 현재수보다 스택안에 있는 큰수 싹다 정리
    if (S.empty())
      ans[i] = -1;
    else
      ans[i] = S.top();
    S.push(a[i]);
  }
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}

아직 못풀어서 바킹독 해답코드 들고옴. 배열 역순으로 접근해서 기준 숫자보다 큰 숫자를 다 없앤다.