[BOJ] 1874 스택 수열 (C++)

1. 문제 링크

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

 

2. 문제 접근

- 특정 수가 나오기 위해서는 우선, 그 수보다 작은 값이 먼저 등장해야한다.

- 예를들어, 5라는 숫자가 나오기 위해서는 1,2,3,4가 먼저 등장해야 한다. (이미 나간 경우를 포함한다.)

- 다음 나와야 할 값을 기록해서, 입력받은 수보다 작으면 계속 스택에 넣어준다.

 

- 위와 같은 형태를 띈다.

- 이때, 스택의 꼭대기 값을 확인해서 같은 값이면 뺀다.

 

- 만약 같은 값이 아닌 경우,  연산이 불가능한 상황이므로, 이를 처리해주면 된다.

 

3. 문제 풀이

- 현재 들어가야 하는 값과 입력 받은 값을 비교한다.

- 만약 입력 받은 값이 더 크다면, stack에 입력 받은 값까지 push한다.

- 이후, 스택에 top 값과 비교해서 같으면 pop, 다르면 impossible을 처리한다.

- 유의할 점은 불가능한 경우에 대한 체크로, 마지막 모든 연산이 끝났을때, stack에 값이 남아있는 경우도 고려한다.

 

4. 소스 코드(C++)

#include <iostream>
#include <string>
#include <stack>
using namespace std;
stack <int> stk;
string answer = "";
int main(void)
{
	int n;
	int now_value = 1;
	bool impossible = false;
	cin >> n;
	while (n--)
	{
		int target;
		cin >> target;
		while (now_value <= target) // 현재까지 저장된 전적이 있는 값을 기록 후, 그 값보다 낮으면 계속 저장.
		{
			stk.push(now_value);
			now_value++;
			answer += '+';
		}
		if (!stk.empty() && target == stk.top()) // 스택에 top에 있는 값이면 pop을 하여 처리
		{
			stk.pop();
			answer += '-';
		}
		else if (!stk.empty() && target != stk.top()) // 스택에 top에 있는 값이 
		{
			impossible = true;
			break;
		}
	}
	if (!stk.empty()) // 위 작업을 끝냈는데 스택에 뭔가 남아있다면 불가능한 경우.
	{
		impossible = true;
	}
	if (impossible == true)
	{
		cout << "NO";
	}
	else
	{
		for (int i = 0; i < answer.length(); i++)
		{
			cout << answer[i] << "\n";
		}
	}
}