[BAEKJOON] 1874번 스택 수열

문 제

 

소 스  코 드

#include <iostream>
#include <stack>
#include <vector>

int main() {
	int N;
	std::stack<int> st;
	std::vector<char> v;
	v.reserve(1'000'000);


	std::cin >> N;
	int* seq{ new int[N] };

	for (int i = 0; i < N; ++i) std::cin >> seq[i];

	int cnt{ 1 }, index{ 0 };
	while (true) { 
		if (st.empty() && (N == index)) break;
		else if (!st.empty() && (seq[index] == st.top())) {
			st.pop();
			v.emplace_back('-');
			++index;
		}
		else {
			if (seq[index] < cnt) {
			std::cout << "NO";
			return 0;
			}
			st.push(cnt);
			v.emplace_back('+');
			++cnt;
		}
	}

	for (const auto& a : v) std::cout << a << '\n';


	delete[] seq;
	return 0;
}

 

풀 이

 

• 1 ~ n 까지 숫자를 원하는 수열 seq[n]으로 만들기 위해서는,
  1 ~ seq[0] 까지 push( )를 하고, stack의 top( )이 seq[0]과 같을 때 pop( )을 해주면 된다. [ 반 복 ]

• 만약, 스택이 비어있고, 모든 수열을 찾았다면 vector에 저장한  ' - ', ' + '을 저장한 정보를 화면에 출력한다.

• 만약, seq[n] 의 내부의 값이 cnt를 넘어갈 경우 수열을 만든느 것이 불가능하다.
  seq[5] { 1, 2, 5, 3, 4 } 의 경우 1이 push( ) 하고 pop( )을 하고, 2가 push( ) 하고 pop( )을 한다.
  그리고, {3, 4, 5} 순으로 push가 되는데 5가 pop이 되고, 3 4를 만들어야 하지만, 4 3 순으로 스택에서 나오기 때문에 불가능하다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/1874

1874번: 스택 수열