[BOJ 1874] 백준 스택 수열 풀이 - C++

사용언어 :  C++

 

 

문제풀이

- 배열에 우선 입력값을 저장한다

- stack을 이용해 배열과 동일한 수열을 만들 수 있는지 판별한다 

-(+,-는 vector값에 차례로 대입 : push할 땐 +, pop할 땐 -)

- 마지막까지 stack에 값이 남아있으면 수열을 만들 수 없음. 비어있을 땐 vector값 차례로 출력

 

(1) 배열에 입력 값 차례대로 대입

	cin >> n;
	for (int i = 0; i < n; i++) //n번 입력받기
		cin >> a[i];

 

(2) stack 을 이용해 판별하기

for (int i = 1; i <= n; i++) {
		stk.push(i); //stack에 값 push할 땐
		ret.push_back('+'); //vector에 + push
        
        //stack이 비어있지 않고, 현재 배열 값과 stack top이 같을 땐 pop해주기
		while (stk.size() && stk.top() == a[idx]) { 
			idx++; 
			stk.pop(); //stack에서 pop할 땐
			ret.push_back('-'); //vector에 - push
		}
	}

 

(3) stack 비어있으면, vector 출력. 존재하면 "NO"출력

if (stk.size()) cout << "NO\n";
	else for (char a : ret)cout << a << "\n";

 

 

전체코드

 

#include <iostream>
using namespace std;
#include<stack>
#include<vector>
int n, a[100001], idx;
stack<int>stk;
vector<char>ret;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		stk.push(i);
		ret.push_back('+');
		while (stk.size() && stk.top() == a[idx++]) {
			 stk.pop(); ret.push_back('-');
		}
	}
	if (stk.size()) cout << "NO\n";
	else for(char a : ret)cout << a << "\n";
}

 

 

 

총평

전에 풀어봤던 문제였는데 오랜만에 다시 푸니까 역시나 하나도 기억나지 않고 처음 푸는 것처럼 어려웠다 ㅜㅜㅋㅋㅋ 스택 수열 개념 자체가 이해하기 어려웠다. 문제를 풀면서 이해한 느낌.. 스택 자체는 이해하기 어렵지 않았는데 나아가서 스택을 응용한 스택 관련 문제를 풀면 새삼 어려워진다 ...

---

문제 출처

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

1874번: 스택 수열