[C/C++] 백준 1874번 - 스택 수열
백준 1874번 스택 수열
https://www.acmicpc.net/problem/1874
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
● 스택의 후입선출 구조를 이용하는 문제
● 현재 수열 값 >= 자연수
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';
}
}
}