[210331][백준/BOJ] 1874번 스택 수열

문제

입출력

---

풀이

문제를 이해하지 못하다가 유튜브에서 설명을 듣고 문제를 이해하였다.
https://www.youtube.com/watch?v=byCxMbgzEVM&t=10s&ab_channel=%EC%BD%94%EB%8D%B0%ED%92%80

1. 둘째줄에 4를 입력받으면 스택에 1부터 4까지 push하고 마지막 4를 pop한다. push를 4번 했으므로 + + + + 를 출력하고 pop을 한번 해서 - 를 출력한다.

2. 다음 입력값은 3이고 스택의 top이 3이므로 pop을 하게 되며 - 를 출력한다.

3. 다음 입력값은 6이고 스택의 top에는 2가 있으므로 push를 3 4 5 6 하게 된다고 생각하지만 예제 출력을 보면 + + - 가 출력된 것을 볼 수 있다. 이는 우리가 스택에 push 된 최대값도 신경을 써줘야 한다는 것을 의미한다. 6이 입력되기 전까지 스택에 push 된 최대값은 4였고 따라서 5 6이 push 되며 6이 pop 되면서 스택에는 1 2 5가 남게 된다.

4. 8도 6가 마찬가지로 + + -를 하게 되며 스택에는 1 2 5 7이 남게 된다.

5. 다음 입력값들은 7 5 2 1이며 pop을 4번 하게 되며 종료된다.

6. 만약 입력값이 스택의 top 보다 작다면 이는 불가능한 경우이며 이때는 NO를 출력하고 프로그램을 종료해야 한다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);	
	
	int tc;
	cin >> tc;

	stack<int> S;
	vector<char> V;
	int max = 0;
	
	while (tc--)
	{
		int n;
		cin >> n;

		if (max < n)
		{
			for (int i = max + 1; i <= n; ++i)
			{
				S.push(i);
				V.push_back('+');
			}
			max = S.top();
			S.pop();
			V.push_back('-');
		}
		else if (n == S.top())
		{
			S.pop();
			V.push_back('-');
		}
		else if (n < S.top())
		{
			cout << "NO" << '\n';
			return 0;
		}		
	}
	for (auto e : V)
		cout << e << '\n';
}

---

느낀점

이해하는데 꽤 시간이 필요했던 문제였다. 다행히도 유튜브에 문제를 설명해주신 분이 계셔서 풀 수 있었다.
문제를 이해한 다음에 예제에 맞게 문제를 풀고나서 제출을 하니 처음에는 틀렸다고 나왔다.
처음에는 최대값이 입력값보다 작을때만 push를 했던게 아니라 스택이 비어있을때도 push를 했으며

		if (S.empty())
		{
			for (int i = 1; i <= n; ++i)
			{
				S.push(i);
				V.push_back('+');
			}
			max = S.top();
			S.pop();
			V.push_back('-');
		}

이 코드가 맨 위에 있던 코드였다. 입력값이 1 2 같은 경우에 + -가 출력되고 스택이 empty 상태가 되므로 + + -가 출력되는 상황이 발생하였다.
따라서 max < n 인 경우를 맨 상단에 올렸으며 이를 if ~ else if 구조로 묶었다. 그리고나서 실행시켜 보면서 스택이 empty인 조건은 필요가 없다는것을 알게 되었으며 최종 코드가 나오게 되었다.

여러 문제를 풀다보니 예제 케이스가 정상 출력 되어서 제출을 하면 틀렸다고 나오는 경우가 많다. 문제를 더욱더 꼼곰하게 읽으며 어떤 예외가 존재할지 어떤 점을 더 신경써야 할지 계속 고민하며 문제를 풀어야 할거 같다.