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

안녕하세요. 오늘 풀어볼 문제는 스택 수열입니다.

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

 

직관적으로 이해는 되지만 막상 구현할 때 멈칫하게 되는 문제에요.

저는 배열로 간단한 스택을 만들어 사용했지만 stl을 사용하셔도 무방합니다.

 

문제에서 중요한 부분만 짚어 보겠습니다.

 

1. NO를 출력하는 조건

NO를 출력하는 조건을 한 마디로 설명하자면

'이미 버린 수를 뽑는 경우' 입니다.

 

스택에서 입력된 수를 뽑을 때는 '입력된 수까지 채운 다음 pop' 하거나, '입력된 수가 나올 때까지 pop' 해야 합니다.

아래 코드에서는 항상 스택을 채우는 작업 다음에 빼는 작업을 하기 때문에 '입력된 수가 나올 때까지 pop'만 고려해주면 되겠죠.

 

그런데 만약 스택의 top이 입력된 수보다 작다면 이미 입력된 수는 버려졌다는 의미겠네요.

 

2. 입력에 따른 출력 방법

입력된 수를 뽑는 연산을 제외하면, 하나의 입력에 대해서 항상 하나의 연산만 수행할 수 있습니다.

다음에 스택에 push할 수를 seq라고 했을 때 입력된 수가 seq보다 크다면 push만, seq보다 작다면 pop만 수행하겠네요.

 

그렇다면 우리가 하나의 입력에 대해 알아야 할 정보는 어떤 연산인지, 몇 번 수행했는지가 됩니다.

저는 op 배열을 만들어 push는 +1로, pop은 -1로 연산 종류와 횟수를 저장했어요.

 

출력을 할 때는 op 배열에 맞춰서 +와 -를 출력해주고 입력된 수를 뽑는 -를 출력해주면 되겠네요.

 

아래는 코드 전문입니다.

#include <iostream>
using namespace std;

int n, idx = 0, seq = 1;
int s[100005], op[100005];

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		while (num >= seq) {
			s[idx++] = seq++;
			op[i]++;
		}

		while (1) {
			idx--;

			if (idx < 0 || s[idx] < num) {
				cout << "NO";
				return 0;
			}

			if (s[idx] == num) {
				s[idx] == 0;
				break;
			}

			s[idx] == 0;
			op[i]--;
		}
	}

	for (int i = 0; i < n; i++) {
		char c;
		if (op[i] > 0) {
			c = '+';
		}
		else {
			c = '-';
			op[i] *= -1;
		}

		for (int j = 0; j < op[i]; j++)
			cout << c << '\n';
		cout << '-' << '\n';
	}
}