[백준 1874번] 스택 수열

https://www.acmicpc.net/problem/1874 

1874번: 스택 수열

풀이) 

스택의 개념을 이용하여, 만들어야하는 첫번째 idx 값이 될때까지 스택에 값을 넣고 만들어야할 값을 찾으면 값을 빼주고 그 다음 만들값을 찾으면 된다. 여기서 오름차순으로 들어가기때문에 그 다음값은 방금 뺀 값보다 1작은 값이 스택의 맨 위에 위치해있는데 이 경우가 아니면 무조건 만들 수 없는 경우이기에 bool값을 통해 처리하고 break로 종료시켜주었다.

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

int n, num = 1, goal_idx = 1, stack_idx = 1, flag = false;
int goal[100001], stack[100001];
vector<char> ans;

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

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> goal[i];

	while (num <= n || stack_idx > 1)
	{
		if (goal[goal_idx] >= num)
		{
			ans.push_back('+');
			stack[stack_idx] = num;
			stack_idx++;
			num++;
		}
		else if (goal[goal_idx] < num)
		{
			if (stack[stack_idx - 1] != goal[goal_idx])
			{
				flag = 1;
				break ;
			}
			ans.push_back('-');
			stack_idx--;
			goal_idx++;
		}
	}
	if (flag)
		cout << "NO\n";
	else
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << "\n";

	return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!