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

문제

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

1874번: 스택 수열

소스코드

#include <stack>
#include <iostream>
using namespace std;
int seq[100000];
char result[200000];
int main(void) {
	//input
	int N; cin >> N;
	for (int n = 0; n < N; n++) {
		scanf("%d", &seq[n]);
	}
	//perform
	int num = 1; int seq_idx = 0;
	stack<int> st;
	bool complete = true;

	while (seq_idx < N) {
		if (st.empty() || st.top() < seq[seq_idx]) {
			st.push(num); num++;
			result[num + seq_idx - 2] = '+';
		}
		else if (st.top() == seq[seq_idx]) {
			seq_idx++;
			st.pop();
			result[num + seq_idx - 2] = '-';
		}
		else {
			complete = false;  
			break;
		}
	}
	//output
	if (complete) {
		for (int i = 0; i < 2 * N; i++) printf("%c\n", result[i]);
	}
	else {
		printf("NO\n");
	}
}

코드설명

1. seq 배열에 수열을 입력 받습니다. (cin, cout으로 하면 시간초과)

2. num은 stack에 들어갈 숫자를 의미하고, seq_idx는 수열에서 비교할 인덱스를 의미합니다.

3. 수행을 할 때 4가지의 경우가 있습니요.

• case1) 스택이 빈 경우
• case2) 스택의 top 값이 다음에 와야할 수열의 값과 같은 경우
• case3) 스택의 top 값이 다음에 와야할 수열의 값보다 작은 경우
• case4) 스택의 top값이 다음에 와야할 수열의 값보다 큰 경우

4. case1번과 case3번의 경우에는 스택에 다음값(num)을 넣어주면 되고, case2번의 경우에는 스택에서 pop을 수행하면 됩니다. case4 같은 경우는 더 볼 필요가 없기 때문에 반복문을 빠져나오면 됩니다.