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

문제 링크

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

 

문제 정보

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

풀이

 굉장히 해결하기 어려운 문제였다. 예제 1번을 보고 문제를 이해해보자.

 

 8 4 3 6 8 7 5 2 1 을 입력했다고 하자. 따라서 처음에 4를 수열에 넣어야 한다. 그 과정은 아래와 같다.

1.  1 2 3 4를 스택에 push 한다.
2.  스택에서 4를 pop 해서 수열에 넣는다. (스택에는 1 2 3이 남는다.)

그리고 3을 수열에 넣어야 한다. 

1.  스택에서 3을 pop 해서 수열에 넣는다. (스택에는 1 2가 남는다.)

그 다음에 6을 수열에 넣어야 한다.

1.  5 6을 스택에 push 한다.
2.  스택에서 6을 pop 해서 수열에 넣는다. (스택에는 1 2 5가 남는다.)

그리고 8을 수열에 넣어야 한다.

1.  7 8을 스택에 push 한다.
2.  스택에서 8을 pop 해서 수열에 넣는다. (스택에는 1 2 5 7이 남는다.)

그 다음에 7을 수열에 넣어야 한다.

1.  스택에서 7을 pop 해서 수열에 넣는다. (스택에는 1 2 5가 남는다.)

그리고 5를 수열에 넣어야 한다.

1.  스택에서 5를 pop 해서 수열에 넣는다. (스택에는 1 2가 남는다.)

그 다음에 2를 수열에 넣어야 한다.

1.  스택에서 2를 pop 해서 수열에 넣는다. (스택에는 1이 남는다.)

그리고 1을 수열에 넣어야 한다.

1.  스택에서 1을 pop 해서 수열에 넣는다. (스택이 비었다.)

 

소스 코드

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	stack<int> S;
	vector<char> result;
	int idx = 1;
	
	while (n--) {
		int num;
		cin >> num;
		
		while (idx <= num) {
			S.push(idx);
			idx++;
			result.push_back('+');
		}
		
		if (S.top() == num) {
			S.pop();
			result.push_back('-');
		} else {
			cout << "NO";
			return 0;
		}
	}
	
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << '\n';
	}
	
	return 0;
}