백준 1874. 스택 수열

스택 수열

스택 응용 문제

1. 간단 설명

---

1~n 사이의 숫자를 스택에 넣었다 빼서

주어지는 수열을 만들 수 있는지 구하는 문제

2. 문제 분석

---

• 글로만 봐서는 이해가 잘 안가므로 그림으로 설명함

예제 1 - 4 3 6 8 7 5 1 만들기

• 먼저 수열의 첫번째 원소인 4를 구해야하므로, 1,2,3,4를 스택에 넣는다(+,+,+,+)

• 4를 뺀다(-)

• 3도 뺀다(-)

• 6을 구해야하는데, 스택의 TOP이 6이 아니므로, 5, 6을 추가한다 (+,+)
• 아까 4까지 넣었으므로, 5부터 추가해야함(중요)

• 6을 뺀다(-)

• 8을 구해야하는데, 스택의 TOP이 8이 아니므로, 7, 8을 추가한다(+,+)
• 아까 6까지 넣었으므로, 7부터 넣는다

• 차례대로 쭉 pop하면, 목표 수열이 구해진다(-,-,-,-,-)

• 해서 ++++--++-++----- 라는 출력이 구해진 것

예제 2 - 1 2 5 3 4 만들기

• 1 넣었다가 빼고
• 2 넣었다 빼고
• 5를 구해야하므로, 3, 4, 5 를 넣는다
• 이후 5를 뺀다
• 그러나 3이 4보다 아래 있으므로 해당 수열을 구하는 것이 불가능하다

상세 설명

• 즉, 해당 수열을 구하기 위해서는, 스택의 top에 해당 수가 있는지 확인해야함
• 만약 지금 구해야하는 수 보다 스택의 top이 작다면
  • 스택에 같은 값이 나올때까지 수를 증가시키며 push한다
• 반대로 크다면
  • 예제 2번처럼 불가능한 경우임

필요 변수

• 수열의 개수 int n(1<=n<=100,000)

• 정답을 기록해둘 vector<char> ans

• 스택 stack<int> st

• 현재 어떤 수를 찾고있는지 받을 int num

• 몇번까지 넣었는지 기록할 int cnt

3. 소스코드

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

using namespace std;

int N;
vector<char> ans;
stack<int> st;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N;
	int cnt = 1;
	for (int i = 0; i < N; i++) {
		int num; cin >> num;

		while (cnt <= num) {
			ans.push_back('+');
			st.push(cnt++);
		}

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

	for (auto e : ans) {
		cout << e << "\n";
	}

	return 0;
}

• 문제 이해와 아이디어를 떠올리는게 어려웠던 문제

• 스택의 특징인 FIFO가 중요한 문제였음