스택으로 수열 만들기

* Do it 코딩테스트를 참고하였습니다. - 백준 온라인 저지 1874번

 

 스택은 LIFO (Last - In - First - Out)의 형태를 가진 선형 자료구조입니다. 이 문제는 문제 그대로 스택을 이용하여 수열을 만들어내는 문제입니다. 1부터 시작하는 자연수를 스택에 값을 넣고, 빼내어 입력으로 주어지는 수열들을 출력하는 문제입니다. 

 

 우선 문제를 풀기 위해서 스택에 Push/Pop을 하는 조건을 만들어야 할 것입니다. 우선 스택안에 출력해야하는 숫자가 들어있어야 하므로 (수열 값) > top()인 동안에는 스택에 Push를 해주며 +를 출력할 것입니다. 그러다 값이 top()이 되는 순간 Pop을 해주며 -를 해주면 될 것입니다. 수열 값 < top() 인 경우는 pop을 해도 입력값으로 들어온 수열을 만들 수 없기 때문에 NO를 출력해주면 될 것입니다.

 

 위의 설명을 토대로 코드를 짜게 되면 이렇습니다.

void solution_011()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	vector<int> list(N, 0);
	vector<char> resultV;

	for (auto& c : list)
		cin >> c;

	int num = 1;
	stack<int> Stack;
	bool result = true;

	for (int i = 0; i < N; i++)
	{
		if (num <= list[i])
		{
			while (num <= list[i])
			{
				Stack.push(num++);
				resultV.push_back('+');
			}
			Stack.pop();
			resultV.push_back('-');
		}
		else
		{
			int temp = Stack.top();
			Stack.pop();

			if (temp > list[i]) {
				cout << "NO";
				result = false;
				break;
			}
			else
			{
				resultV.push_back('-');
			}
		}
	}
}

이상으로 '스택으로 수열 만들기'에 대한 설명을 마치겠습니다. 포바~!