[백준 1874번 C++] 스택 수열

1. 문제 링크

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

1874번: 스택 수열

 

 

 

2. 문제 설명

스택 수열을 입력받은 후 push와 pop으로 해당 수열을 만들 수 있는 경우 push는 +, pop은 -로 표현하고,

불가능한 경우 NO를 출력하는 문제입니다.

 

 

 

3. 소스코드

BOJ 1874번 스택 수열 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, num, cnt = 1;
	stack<int> s;
	string result = "";
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num >= cnt) {
			while (num + 1 != cnt) {
				s.push(cnt++);
				result += "+\n";
			}
			s.pop();
			result += "-\n";
		}
		else {
			if (s.top() == num) {
				s.pop();
				result += "-\n";
			}
			else {
				result = "NO";
				break;
			}
		}
	}
	cout << result;

	return 0;
}

먼저 스택에 넣을 수 cnt를 1로 초기화합니다.

 

17번 라인 if문을 통해 입력받은 수 num이 cnt와 같거나 크면

cnt가 num과 같아질 때 까지 스택에 cnt를 push하고 result에 +를 이어 붙입니다.

그리고 해당 수를 출력하기 위해 pop을 하고 result에 -를 이어 붙입니다.

예를 들어 처음에 4를 입력받으면 스택에 1, 2, 3, 4를 push하므로 +를 4번 출력하고, 4를 pop하고 -를 1번 출력합니다.

 

25번 라인 else문을 통해 입력받은 수 num이 cnt보다 작으면

스택의 top이 num과 같은지 확인하고, 같으면 해당 수를 출력하기 위해 pop을 하고 result에 -를 이어 붙입니다.

스택의 top이 num과 같지 않으면 주어진 스택 수열을 만들 수 없으므로 result에 NO를 저장하고 for문을 탈출합니다.

 

최종적으로 result를 출력하면 됩니다.