[c++] 백준 1874 스택 수열

백준 단계별로 풀어보기 [스택] 스택 수열

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

1874번: 스택 수열

 

[풀이]

1부터 n까지의 수를 스택에 push 하고, push 할 때마다 '+'를 부호 배열에 저장한다. 처음 수열을 입력받은 배열의 수와 스택의 top이 일치하는 동안(또한 스택이 empty가 아닌 동안) 스택을 pop하고 '-'를 부호 배열에 저장한 후 수열 배열 인덱스를 증가해준다. for문이 끝난 후에 스택이 비어있지 않다면 스택을 이용해 해당 수열을 만들 수 없다는 것이므로 "NO"를 출력하고, 아니라면 배열을 출력한다.   

 

[코드]

#include<iostream>
#include<algorithm>
#include<string>
#include<stack>

int main() {
	//1 2 5 3 4 / 1 push 1 pop 2 push 2 pop 3 push 4 push 5 push 5 pop 4 pop 3 pop
	// 4 3 6 8 7 5 2 1 / + + + + - - + + - + + - - - - -
	int n;
	std::cin >> n;
	std::stack<int> s;
	int* arr = new int[n];
	char* str = new char[2*n];
	for (int i = 0; i < n; i++) {
		std::cin >> arr[i];
	}

	int j = 0, cnt = 0;
	for (int i = 1; i <= n; i++) {
		s.push(i);
		str[cnt++] = '+';
		//std::cout << "+" << "\n";
		while (!s.empty() && arr[j] == s.top()) {
			s.pop();
			str[cnt++] = '-';
			//std::cout << "-" << "\n";
			j++;
		}
	}

	if (!s.empty()) {
		std::cout << "NO";
	}
	else {
		for (int i = 0; i < 2 * n; i++) {
			std::cout << str[i] << "\n";
		}
	}

	delete[] arr, str;
	return 0;
}