[C++] 백준 - 스택 관련 문제들

오랜만에 글을 써본다.
PS능력이 너무 떨어지는 것 같아서 요즘 다시 파는 중인데...쉽지가 않다.
다시 차근차근 기초 자료구조 관련 문제부터 풀어보았다.

스택(Stack)이란?

관련 학부생이나 이쪽으로 공부를 조금이라도 해봤다면 들어봤을 법한 자료구조이다.
데이터들은 스택에 들어온 순서에 따라 나갈 수 있다.
즉, 입구와 출구가 같은 느낌이다.
흔히들 FIFO(First In, First Out)라고 부르는 성질을 가지고 있다.
PS에서도 이 특징을 필요로 하면 사용하면 되겠다.

1. #1874 스택 수열

풀이 과정

어차피 오름차순으로 push하기 때문에 고려할 사항이 많지 않다.
1부터 push하고 스택의 top에 원하는 원소가 있다면 pop을 해주면 된다.

만약 찾는 원소가 top에 없다면?
그럼 바로 NO를 출력하고 종료하면 된다.
오름차순으로 push하기 때문에 한 번 막히면 답이 없는 것이기 때문이다.
각 연산에 해당하는 기호를 출력해야 하므로, 정답을 저장할 vector도 따로 만들었다.

정답 코드

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

int arr[100010];

int main() {

	int N;
	int cnt = 1;

	scanf("%d", &N);

	stack <int> s;
	vector <char> ans;

	for (int i = 0; i < N; i++)
	{
		int x;
		 
		scanf("%d", &x);

		while (cnt <= x)
		{
			s.push(cnt);
			cnt += 1;
			ans.push_back('+');
		}

		if (s.top() == x)
		{
			s.pop();
			ans.push_back('-');
		}

		else
		{
			printf("NO");
			return 0;
		}
	}

	for (int i = 0; i < ans.size(); i++)
		printf("%c\n", ans[i]);

	return 0;
}

2. #2493 탑

풀이 과정

스택을 이용해서 탑의 높이를 입력받는다.
그리고 탑의 순서를 나타내는 값(인덱스)과 높이를 나타내는 pair로 스택을 선언했다.

입력받는 값의 크기에 따라 두 가지 경우로 나눌 수 있다.

1. 기존의 탑이 더 높을 경우
   처음부터 진행하면 현재 top에 있는 값이 최대값일 것이다.
   그리고 다음에 올 탑의 높이가 자신보다 클지 작을지 미리 알 수 없다.
   따라서 pop을 하지 않고 넘긴다.

2. 새롭게 입력한 탑이 더 높을 경우
   왼쪽에 있는 탑에서는 레이저 신호를 받을 수 없다.
   따라서 stack을 pop해준다.

각 반복이 끝날 때마다 신호를 받을 수 있는 탑의 후보가 stack에 저장된다.
비교 후, 해당하는 탑의 위치를 알맞게 출력해주면 된다.

정답 코드

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

stack <pair<int, int>> s;

int main() {
	int N, input;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &input);

		while (!s.empty())
		{
			if (s.top().second > input)
			{
				printf("%d ", s.top().first + 1);
				break;
			}

			s.pop();
		}

		if (s.empty())
			printf("0 ");

		s.push(make_pair(i, input));
	}

	return 0;
}

3. #6198 옥상 정원 꾸미기

풀이 과정

#2493 탑과 유사한 문제이다.
방향 정도만 반대인데, 자신의 오른쪽만 볼 수 있고 높이가 같아도 볼 수 없다.
풀이과정은 아래와 같다.

1. 첫 번째부터 stack에 push한다.
2. 현재 top보다 입력값이 더 크다면 top의 관리인은 어떤 옥상도 확인할 수 없다. 따라서 top을 pop해준다.
3. 현재 top보다 입력값이 더 작다면, stack에 push한다. (볼 수 있는 거니까)
4. 각 입력에 대해서 1 2 3 을 반복하고, 각 과정에서의 stack의 size에서 1을 뺀 값(자기 자신을 제외하고 볼 수 있는 옥상)을 누적해서 더해준다.

정답 코드

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

int main() {
	ios::sync_with_stdio(false);

	stack <long long int> height;

	int N;
	long long int ans = 0;
	long long int input;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> input;

		while (!height.empty())
		{
			if (height.top() <= input) height.pop();
			else break;
		}

		height.push(input); 
			
		ans += height.size() - 1;
	}
	

	cout << ans;

	return 0;
}

피드백

당연하지만 stack의 성질에 알맞게
현재 최신값과의 비교가 필요한 경우에 stack을 많이 썼다.
최신값은 곧 stack에서의 top을 의미한다.
항상 push된 순서에 맞게 pop할 수 있으므로, 누적해서 입력받은 데이터들끼리의 비교가 필요할 때 쓰면 좋겠다.