[C++ 백준] 1874 스택 수열

블로그에 올리는 모든 문제 풀이는 깃허브에 올려져 있습니다.

---

문제 설명

• 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다.
  둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다.
  물론 같은 정수가 두 번 나오는 일은 없다.

---

풀이 전략

• 입력한 값까지 수를 순서대로 쌓는다. (스택 사용)
• 스택에 들어간 마지막 숫자와 입력한 숫자가 같다면 빼낸다.
  같지 않다면 불가능!!
• 결과를 출력 할 때 endl로 인한 시간 초과가 나서 특수문자 '\n'을 사용하였다.

소스 코드

#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
int main()
{
	stack<int> s;
	vector<char> result;
	int cnt = 1;
	int n;
	cin >> n;
 
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
 
		while ( cnt <= x )
		{
			s.push(cnt);
			cnt += 1;
			result.push_back( '+' );
		}
 
		if (s.top() == x)
		{
			s.pop();
			result.push_back( '-' );
		}
		else
		{
			cout << "NO";
			return 0;
		}
	}
 
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << '\n'; //!< endl로 인한 시간초과 조심
	}
}

---

링크

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net