백준 1874 - 스택 수열

Updated:

C++

1874번 - 부등호

문제

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 문제 출처

접근 방법

주어진 수가 나올 때 까지 Index를 증가시키며 Push한다.
이후 stack의 최 상단이 주어진 수가 나오면 pop을 하고, 이 최상단의 값이 주어진 수가 아니면 이전에 그 수가 건너 띄어진 것이므로 No를 출력하며 종료한다.

코드

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

using namespace std;
int n;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int idx = 1, curN;
	stack<int> s;
	bool chk = true;
	vector<char> c;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> curN;
		while(idx <= curN) {        //주어진 수가 나올 때 까지 push
			s.push(idx);
			idx++;
			c.push_back('+');  
		}   
		if (s.top() == curN) {      //주어진 수가 확인되면 pop
			s.pop();
			c.push_back('-');
		}
		else {                      
			chk = false;
			cout << "NO" << "\n";
			break;
		}

	}
	if (chk) {
		for (int i = 0; i < c.size(); i++)
			cout << c.at(i) << "\n";
	}

	return 0;
}

후기 및 개선할 점