0x06 - 스택

스택의 정의

선입후출 FILO 구조임

1.원소의 추가와 제거가 O(1)

2.제일 상단의 원소 확인이 O(1)

3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

구현

배열 혹은 연결리스트를 이용해 구현 가능

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

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x) {
	dat[pos++] = x;

}

void pop() {
	if(pop >0)
		pos--;
}

int top() {
	return  dat[pos-1];
}

void test() {
	push(5); push(4); push(3);
	cout << top() << '\n'; // 3
	pop(); pop();
	cout << top() << '\n'; // 5
	push(10); push(12);
	cout << top() << '\n'; // 12
	pop();
	cout << top() << '\n'; // 10
}

int main(void) {
	test();
}

STL stack

연습문제

10828 . 스택

#include <bits/stdc++.h>

using namespace std;

int main()
{
	stack <int> s;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string command;
		cin >> command;
		if (command == "push")
		{
			int input;
			cin >> input;
			s.push(input);
		}
		else if (command == "pop")
		{
			if (s.empty())
			{
				cout << -1 << '\n';
			}
			else
			{
				cout << s.top() << '\n';
				s.pop();
			}
		}
		else if (command == "size")
		{
			cout << s.size() << '\n';
		}
		else if (command == "empty")
		{
			cout << s.empty() << '\n';
		}
		else if (command == "top")
		{
			if (s.empty())
			{
				cout << -1 << '\n';
			}
			else
			{
				cout << s.top() << '\n';

			}
		}
	}
}

기초적인 STL에 구현된 스택의 명령어들을 활용해 볼수있는 문제였다.

10773 . 제로

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	stack <int> s;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;
		if (input == 0)
			s.pop();
		else
			s.push(input);
	}
	int ans = 0;

	while (!s.empty())
	{
		ans += s.top();
		s.pop();
	}

	cout << ans << '\n';
}

n만큼 입력을 받으면서 0일때는 pop을 아니라면 push를 해준다. 입력을 모두 받고난뒤 스택이 빌때까지 pop하며 스택에있는 값을 모두 더해주면된다.

1874 스택 수열

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	stack <int> s;
	vector <char> v;
	int n;
	cin >> n;


	int cnt = 1;
	while (1)
	{
		int input;
		cin >> input;


		if (!s.empty() && s.top() >input)
		{
			cout << "NO\n";
			return 0;
		}

		for (int i = cnt; i <= input; i++)
		{
			cnt++;
			s.push(i);
			v.push_back('+');
		}
		s.pop();
		v.push_back('-');
        if (cnt > n && s.empty())
			break;
        
	}

	for (char c : v)
	{
		cout << c << '\n';
	}
}

수열을 저장할 스택과 +-기호를저장할벡터를 선언한다 while문 을통해 수열에 나올 인자를 입력받는다 만약 이숫자가
현재 스택이 비어있지않고 만약 스택의 Top이 input보다 크다면 이 수열은 불가능한 수열이다.

예를 들어보자면 현재 스택의 탑이 4인경우 7이 들어온다면 567을 넣고 7을 pop하면된다. 하지만 2가들어온경우 3과4를 pop해야되기때문에 문제에서 제시된 수열은 완성할수없게된다.

만약 이조건에 걸리지않았다면 현재 마지막으로 넣은 숫자 +1 인 cnt부터 input까지 스택에 push한뒤(이때 벡터에 +기호를 집어넣는다) 스택을 pop해주고 -기호도 넣어준다.

그리고 cnt가 n보다 크다 즉 n까지 모두 들어간 상태이고 스택이 비어있다면 수열을 모두 완성한경우 이므로 벡터에 입력된 기호들을 출력해주고 종료한다.

2493 . 탑

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	stack <pair<int, int>> s;

	int cnt;
	cin >> cnt;
	int ans = 0;


	for (int i = 0; i < cnt; i++)
	{
		int h;
		cin >> h;

		while (1)
		{
			if (s.empty())
			{
				cout << "0 ";
				break;
			}
			else
			{
				if (s.top().first <= h)
				{
					s.pop();
				}
				else
				{
					cout << s.top().second << ' ' ;
					break;
				}
			}
		}
		s.push({ h,i +1 });
	}
}

스택을 이용해 O(N) 에 문제를 해결해야한다 탑마다 앞에있는 모든 탑을 비교하는 O(N^2)의 경우 시간초과를 맞게된다.

가장 중요한 포인트는 만약 탑의 높이가 들어왔을때 이전탑이 들어있는 스택에서 현재 들어온 탑의 길이보다 낮은 탑들은 필요가없어진다는것이다. 현재 탑의 높이가 더 높기때문에 오른쪽에있는탑에서 쏘는 레이저를 수신할수 없기 때문이다. 이점을 살려서 코드를 짜보면

우선 높이 h를 입력으로 받고 만약 스택이 비어있는 상황이라면(처음 입력이 들어온 상황) 0을출력해주고 넘어간다 만약 스택이 비어있지않다면 스택의 Top의 높이를 현재 들어온 h와 비교해 같거나 작을경우 pop해준다 만약 큰 탑을 만난 경우 그 탑이 레이저를 수신하므로 그탑의 stack.top().second 좌측 기준 몇번쨰 탑인지를 출력하고 넘어가면된다.

마지막으로 반복문을 탈출하고 난뒤에 스택에 입력받은 탑과 순서를 넣어주면된다.

6198 . 옥상 정원 꾸미기

#include <bits/stdc++.h>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	vector <int> v;
	int n;
	cin >> n;

	for (size_t i = 0; i < n; i++)
	{
		int h;
		cin >> h;
		v.push_back(h);
	}
	long long ans = 0;
	stack <int> s;
	for (int i = 0; i < v.size(); i++)
	{
		while (!s.empty() && s.top() <= v[i])
		{
			s.pop();
		}
		ans += s.size();
		s.push(v[i]);

	}

	cout << ans << '\n';

}

우선 빌딩의 높이를 입력받아 벡터의 저장한후 벡터를 앞에서부터 탐색하며 문제를 해결한다 벡터에 해당하는 빌딩을 볼때 그빌딩을 볼수있는 빌딩의 갯수를 더해주는 식으로 정답을 찾는다 그렇게 하기위해 반복문을통해 스택이 비어있지않다면(만약 스택이 비어있다면 s.top()에서 런타임 에러가 발생하므로) 스택의 탑과 현재 보고있는 빌딩의 높이를 비교한다 만약 높이가 같거나 작다면 이빌딩을 볼수없음 으로 pop해준다 그후 스택의 사이즈를 정답에 더해주고 해당 빌딩의 높이를 스택에 push해준다

예시로
10
3
7
4
12
2
이 입력으로 들어온경우

10 스택이 비어있음으로 +0 stack : { 3};
3 top이 3보다 크므로 pop없음 현재사이즈 1 + 1 { 10,3};
7 3은 7보다 작으므로 pop됨 현재사이즈 1 + 1 { 10,7};
4 pop없음 + 2 { 10,7,4};
12 모두 12보다 작아 pop 됨 +0 {12}
2 pop없음 + 1 { 12,2}

그리고 벡터를 모두 탐색했기떄문에 종료되고 답 5가 정확히 출력되는것을 확인할수있다.