1874

들어가는 말

스택에 수를 넣고 주어진 수열을 어떻게 만들 수 있는지를 구하는 문제이다.

예를 들어 수열 '4, 3, 6, 8, 7, 5, 2, 1'이 주어졌을 때, 차례대로 수를 넣어주다가 top이 현재 수와 같으면 pop을 해주면 되는 문제다. 처음에는 문제가 무엇을 말하는지 몰라서 다른 이들의 설명을 찾아봤다.

다른 사람들의 풀이에는 현재 숫자와 받은 수열의 숫자를 비교하는 while문이 있었다. 처음에는 저 while문을 이해할 수 이해하기 어려웠는데, 나는 그저 단순히 스택의 top만 비교해서 빼주거나 넣으면 된다고 생각했기 때문이다. 그러나, 막상 문제를 풀려고 하자 왜 while문이 있는지 알아차렸다.

주어진 n만큼 for문을 돌려야 하는데, 만일 반복문을 n만큼만 돌린다면 스택에다가 숫자를 넣는 게 턱없이 부족하기 때문이다. 즉, cnt와 비교를 해줘서 만일 현재 들어간 숫자가 a보다 작을 경우(스택에 들어간 숫자가 원하는 숫자보다 작을 경우) while문을 돌려서 a만큼 스택에 넣고 a와 같아지면 pop을 하는 형식으로 가야하기 때문이다.

코드 설명

일단 수열의 크기 n을 받는다 그리고 n만큼 for을 돌려주면서 수열의 숫자 a를 받는다.

만일 a가 스택에 들어가야 하는 숫자보다 크거나 같다면(즉, 스택에 숫자 a가 없다면) while문을 돌려서 cnt가 a보다 커질 때까지 스택에 cnt를 넣어주고 cnt를 ++해준다. 그리고 정답을 저장하는 문자열에다가 '+'를 넣어서 스택에 숫자가 들어갔음을 알려준다.

만일 스택의 top과 a가 같다면, 스택에 '-'를 넣어주고 pop을 해준다.

위의 두 조건에 모두 해당하지 않는다면 수열이
불가능하다는 뜻이니까 NO를 출력해주고 0을 return해준다.

0을 return하지 않았다면 for문을 정답이 들어간 벡터만큼 돌려서 출력해준다.

코드

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

using namespace std;

int main() {
	vector<char> v;
	stack<int> st;
	int cnt = 1;
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;

		while (cnt <= a) {
			st.push(cnt);
			cnt++;
			v.push_back('+');
		}

		if (a == st.top()) {
			v.push_back('-');
			st.pop();
		}
		else {
			cout << "NO";
			return 0;
		}
	}

	for (auto vv : v) {
		cout << vv << '\n';
	}
}