백준 1874 : 스택 수열

저세상 개발자 2021. 8. 1. 21:58

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

1. 현재 출력하고자 하는 수(target)가 스택에 삽입될 때까지 cur값을 증가시키며 스택에 추가, 연산 로그 갱신

2. target이 지금 스택에 제일 위에 있는 값과 다르다면 불가능한 경우이므로 break

3. 그렇지 않은 경우 스택에서 pop 작업 수행 후 연산 로그 갱신

해당 for문 수행 후 만약 스택이 비어있지 않다면 정상적으로 종료되지 않은 경우이므로 NO 출력

스택이 비어있다면 연산 로그 출력

#include <iostream>
#include <stack>

using namespace std;

char cpt[200'001];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	int target, idx = 0, cur = 1;

	stack<int> st;
	for (int i = 0; i < n; i++) {
		cin >> target;
		while (target >= cur) {
			st.push(cur++);
			cpt[idx++] = '+';
		}
		if (st.top() != target) 
			break;
		st.pop();
		cpt[idx++] = '-';
	}

	if (!st.empty()) cout << "NO";
	else {
		for (int i = 0; i < idx; i++) {
			cout << cpt[i] << '\n';
		}
	}
	return 0;
}

메모리: 2348 kb

시간: 20 ms