[C/C++] 백준 1874번 - 스택 수열

백준 1874번 스택 수열

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

1874번: 스택 수열

 

    ● 스택의 후입선출 구조를 이용하는 문제   

    ● 현재 수열 값 >= 자연수

        while(수열 값>=자연수){  

               stack.push(자연수);

               자연수++;

               result.push_back('+'); }

            stack.pop();

           result.push_back('-');

      → 만약 현재 수열 값이 4이고 자연수가 1이라면 1,2,3,4를 스택에 push해주고 마지막에 pop을 1회만 하여

           4를 꺼내고 조건문 종료

          

      

  ● 현재 수열 값 < 자연수

      stack.pop();

      if(pop한 값 >= 자연수){

          check = false;

          NO출력

          break;

               }

       else{

                result.push_back('-')   }

 

     

      → 만약 현재 수열 값이 3, 자연수가 5라면 스택에서 3을 꺼낸뒤 현재 수열 값과 스택에서 꺼낸 값이 같으므로

           연산을 계속해서 수행할 수 있음

 

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

int main() {

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

	int n; // 배열의 크기
	cin >> n;

	vector<int>A(n, 0); // 입력 받을 배열
	vector<char>result; // 결과 출력 배열

	int num = 1;// push할 자연수
	stack<int>myArr; // 스택
	bool check = true; // NO의 판단법
	
	for (int i = 0; i < n; i++) {
		cin >> A[i]; // 배열 입력
	}

	for (int i = 0; i < A.size(); i++) {
		
		int su = A[i]; // 현재 배열의 값

		if (su >= num) { // 배열의 값이 num보다 크다면
			
			while (su >= num) {  
				myArr.push(num);
				num++;
				result.push_back('+');
			}
			
			myArr.pop();
			result.push_back('-');
		}
		
		else {
			
			int dx = myArr.top();
			myArr.pop();
			
			if (dx > su) {
				cout << "NO";
				check = false;
				break;
			}
			
			else {
				result.push_back('-');
			}
		}
	}

	if (check) {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << '\n';
		}
	}
}