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

목차.

1. 문제
2. 코드

 

문제

 

백준 1874번 스택수열

 

스택 수열 문제가 처음 잘 이해가 되지 않아 어려웠는데 이해를 한다면 크게 어렵지 않은 문제입니다.

 

예시에서 입력에서 처음 4를 입력하였으니 1에서 4가 되도록 4번의 push(+)를 거친 뒤 마지막에 4를 pop(-) 해줍니다.

다음 수열에 3을 입력하기위해 가장 위에 있는 3을 pop(-) 해줍니다

다음 수열에 6을 입력하기위해 현재 오름차순으로 저장된 값 마지막이 4이니까 두 번을 push 해서 6으로 만든 뒤, pop을 합니다.

이런 과정을 반복하면 됩니다.

 

코드

 

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

stack<int> stk;
string str;
int main() {

	int n, cnt = 1;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		while (cnt <= x) {
			stk.push(cnt);
			str += '+';
			cnt++;
		}
		if (x == stk.top()) {
			stk.pop();
			str += '-';
		}
		else {
			cout << "NO";
			return 0;
		}
	}
	for (char ch : str) {
		cout << ch << "\n";
	}
}

 

n은 입력을 반복하기 위한 수입니다.

cnt는 오름차순으로 정수를 저장하기위한 값으로 push가 될 때마다 1 증가합니다.

현재 cnt의 값이 4이고 3을 입력한다면 반복문을 지나 stack의 가장 위에 있는 값이 3과 같아질 때까지 pop을 반복합니다.

현재 cnt의 값이 4이고 6을 입력한다면 반복문을 통해 4->6이 될때까지 push를 2번 반복합니다.