백준 1874 _ 스택 수열

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

1874번: 스택 수열

---

⭐ 내 소스 코드

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


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int num,n;
	vector<int> answer;
	stack<int> s;
	vector<char> a;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> n;
		answer.push_back(n);
	}
	n = 1;
	for (int i = 0; i < answer.size(); i++) {
		if (s.empty()) {
        	//스택이 비어있는데, 스택에 추가 될 값이 만들어야되는 숫자보다 클 경우
			if (n > answer[i]) {
            	//수열을 완성 할 수 없는 경우라 판단, 종료
				s.push(-1);
				break;
			}
			s.push(n++);
			a.push_back('+');
		}
        //만들어야 되는 숫자보다 스택에 추가 될 값이 작을 경우
		while (n <= answer[i] ){
        	//스택에 값을 계속하여 추가
			s.push(n++);
            //push 연산이 되었으니 +를 저장
			a.push_back('+');
		}
        //스택에 추가 될 수가 만들어야 되는 값보다 클 경우
		while (n > answer[i]) {
			if (s.top() <= answer[i]) {
				break;
			}
            //스택에서 pop될 값이 만들어야 되는 수보다 클 경우
			else if(s.top()>answer[i]){
            	//계속해서 pop을 해준다
				s.pop();
                //pop연산을 하였으니 -를 저장
				a.push_back('-');
			}
		}
        //pop될 값과 만들어야 되는 수가 같으면
		if (s.top() == answer[i]) {
        	//해당 수를 pop하고 -결과 저장
			a.push_back('-');
			s.pop();
		}
	}
    //스택이 비어있으면 수열을 완성한 것으로 판단
	if (s.empty()) {
    	//저장 해두었던 + - 값들을 출력
		for (int i = 0; i < a.size(); i++) {
			cout << a[i] << '\n';
		}
	}
    //비어있지 않으면 수열을 완성 할 수 없는 것으로 판단
	else {
		cout << "NO";
	}

	return 0;
}

 

🙏 문제 풀이

1부터 N까지의 수를 스택에 넣었다가 뽑아내어 늘어 놓음으로써 만들어야 되는 수열은 입력으로 들어오는 수열 (예제 입력 1의 경우 : 4, 3, 6, 8, 7, 5, 2, 1)이다.

 

예제 입력 1의 경우를 살펴보자. 해당 수열에서 가장 처음으로 필요한 수는 '4'이다.

스택에 1, 2, 3, 4를 push 하니, '+ + + +' 라는 출력을 얻게 된다.

스택에 필요한 수인 4가 push 되었으니, 이것을 꺼내어 수열로 만들어야 된다. 4라는 수를 pop하여 - 라는 출력을 얻게 된다.

그 다음으로 필요한 수는 '3'이다. 현재 스택에는 (1, 2, 3)이라는 수가 들어있다. 바로 pop을 하면 3을 얻어 낼 수 있으니 3을 pop하고 -라는 출력을 얻어낸다.

다음으로 필요한 수는 '6'이다. 현재 스택에는 (1, 2)이라는 수가 들어있다. 스택에는 6이라는 값이 존재하지 않으므로 push를 계속해서 해준다. 스택에 (1, 2, 5, 6)이 push가 되고 + +라는 출력을 얻어낸다. 필요한 수인 '6'이 스택에 들어왔으므로 이것을 pop하여 6이라는 숫자를 얻어내고 -의 출력을 얻는다.

위와 같은 과정을 계속하여 반복.