[1874] 백준 알고리즘 : 스택 수열(C++)

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

문제 자체가 이해되지않아, 힘든 문제였다.ㅜㅜ

첫 줄 : 입력 개수(n)
다음 줄 ~ 끝 : 원하는 숫자 순서

스택에 1~n까지 순서대로 숫자가 입력되는데, 이를 처리하여 입력한 순서대로 push(), pop()하면 되는 문제였다.

들어온 숫자가 num, 1~n까지를 t로 제어할때
num > t 이면, 일단 계속 push()
num==t 이면, push()하고 pop()
num < t 이면, num이 이미 스택에 넣어진 숫자라는 뜻이기 때문에
스택의 top()숫자와 같으면 pop() 아니면 더 깊숙히 있는 숫자라 꺼낼 수 없어 NO를 출력하고 끝낸다.
(NO인지 여부는 end로 제어한다.)

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

int main()
{
	int n = 0;
	cin >> n;
	cin.ignore();

	int t = 1;				// 1~n
	int num = 0;			// 입력한 수
	stack<int> st;
	bool end = false;		// 중간에 NO가 나오면 끝내기
	vector<char> result;	// 출력결과 저장

	for (int i = 0; i < n; i++)
	{
		cin >> num;
		while (1)
		{
			if (num > t)
			{
				st.push(t);
				t++;
				result.push_back('+');
			}
			else if (num == t)
			{
				st.push(t);
				t++;
				result.push_back('+');
				st.pop();
				result.push_back('-');
				break;
			}
			else
			{
				if (st.top() == num)
				{
					st.pop();
					result.push_back('-');
				}
				else
				{
					cout << "NO";
					end = true;
				}
				break;
			}
		}
		if (end == true) break;
	}
	if(end == false)
		for (int k = 0; k < result.size(); k++)
		{
			cout << result[k] << "\n";
		}

	return 0;
}

그런데, 처음에 돌렸을때에는 시간초과가 떴었다 ㅜㅜ
검색결과 cout 할 때, endl은 시간을 굉장히 많이 잡아먹는 아이여서 그렇다고 한다.

cout << endl; 대신에 cout << "\n";으로 수정하니까 성공 ^◇^

 

1874번: 스택 수열