백준_1874: 스택수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

배열의 첫번째 값인 4까지 스택에 추가

 

 

스택의 마지막 요소와 배열의 값( 4 )을 비교 후 같음을 확인 후 스택의 마지막요소 제거, 정답배열에 - 추가

 

배열의 두번째 값과 마지막 요소가 같을 때 똑같이 삭제 후 - 추가

4까지 추가했기 떄문에 5부터 스택에 추가 (배열의 값인 6이 될때까지)

6의 값 삭제 후 - 추가

 

이런 과정을 입력받은 숫자의 갯수대로 8번 반복

 

이렇게 스택은 모두 삭제되어 비어있고 정답배열은 이렇게 완성

 

 

여기서 정답배열의 -갯수와 n의 값을 비교해 같다면 정답배열을 출력하고

같지 않다면 연산가능한 배열이 아니기 때문에 NO 를 출력

 

 

 

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
	int n, m, j=1, count=0;
	vector <int> v;			// 입력받을 수열
	vector <char> answer;	// 정답출력할 배열(+ -)
	stack<int> s;

	cin >> n;

	for (int i = 0; i < n; i++) {	//수열 입력
		cin >> m;
		v.push_back(m);
	}

	for (int i = 0; i < n; i++) {
		if ((s.empty() == false) && (s.top() == v.at(i))) {	// 스택에 값 추가 전 pop 하는 경우 
			answer.push_back('-');			//정답배열에 - 저장
			s.pop();
		}
		else {					// 빼내야할 수열까지 스택에 차례대로 집어넣음
			for (j; j <= v[i]; j++) {// 오름차순으로 push해야 하기 때문에 j는 v[i]값으로 증가
				s.push(j);
				answer.push_back('+');
			}
		}
		if ((s.empty() == false) && (s.top() == v.at(i))) {	// 위 pop 하는 if문과 같음
			answer.push_back('-');		// 스택에 값 추가 후 pop 하는 경우 
			s.pop();
		}
	}

	for (int i = 0; i < answer.size(); i++) {		// - 갯수 카운트
		if (answer[i] == '-')
			count++;
	}

	if (count == n) {			//- 갯수가 n개일 경우
		for (int i = 0; i < answer.size(); i++)
			cout << answer[i] << "\n";	//정답출력
	}
	else						// - 갯수가 n개가 아닌경우(연산불가)
		cout << "NO\n";			// NO 출력
	
	return 0;
}