백준 1874번 스택 수열

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

 

아이디어:

1. 스택 사용

2. 입력한 수열과 현재 자연수 (1~n)을 비교

3. 결과를 배열에 저장해서 마지막에 출력

4. 현재 수열 값이 현재 자연수보다 크거나 같으면 값이 같아질 때 까지 계속 push하고 마지막에만 pop

(ex. 백준 예제 입력의 경우, 수열이 4로 시작한다. 자연수는 1이므로, 4에 도달할 때 까지 계속 push후, 마지막에 pop해서 4를 결과 배열에 저장)

5. 현재 수열 값이 현재 자연수보다 작을 때, pop해서 나온 값이 수열 값과 다르면 후입선출의 원리에 의해 수열 만들기가 불가능하다. > NO 출력, flag를 false로 만들고 종료

6. 불가능하지 않다면 pop만 실행

(ex. 백준 예제 입력의 경우에서 4를 pop한 뒤, 수열은 3, 자연수는 5이다. 수열이 자연수보다 작으므로 pop을 실행한다. pop한 결과가 3이고, 수열 값이 3으로 같으므로 그대로 결과 배열에 저장한 뒤 반복문을 진행한다.)

(ex. 백준 두번째 예제의 경우 1, 2까지는 그대로 push, pop. 현재 수열의 값이 5인데, 자연수는 3이다. 스택이 비어있으므로 pop한 값이 5와는 다르다. 따라서 수열 완성이 불가능하다.)

7. 마지막에 결과 배열을 저장한다.

 

// 1874

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

using namespace std;

int main() {

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

	int n, k = 1;
	bool flag = true;
	cin >> n;

	vector<int> A(n, 0);
	vector<char> result;
	stack<int> mystack;

	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

	for (int i = 0; i < A.size(); i++) {
		if (A[i] >= k) {
			while (A[i] >= k) {
				mystack.push(k++);
				result.push_back('+');
			}
			mystack.pop();
			result.push_back('-');
		}

		else {
			int a = mystack.top();
			mystack.pop();
			if (a > A[i]) {
				cout << "NO";
				flag = false;
				break;
			}
			else {
				result.push_back('-');
			}
		}

	}

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

	return 0;

}