2) 백준 1874 - 스택 수열

1874번: 스택 수열 (acmicpc.net)

1874번: 스택 수열

---

2년 전에 풀었지만 왜인지 계속 시간 초과만 뜨던 문제.

 

생각보다 해결법은 간단했다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int num;
	int j = 0;
	int arr[100001] = {0, };
	
	cin >> num;
	
	vector<char> answer;
	stack<int> s;
	
	for(int i = 0; i < num; i++) {
		int cal;
		cin >> arr[i];
	}
	
	// i : 숫자 순서 (1~num)
	// j : 목표 수열 순서 
	// stack : 숫자 순서대로 push 
	for(int i = 1; i <= num;) {
		if(s.empty()) {
			s.push(i);
			answer.push_back('+');
			i++; 
		}
		if(arr[j] == s.top()) {
			s.pop();
			answer.push_back('-');
			j++;
		}
		else {
			s.push(i);
			answer.push_back('+');
			i++;
		}
	}
	
	while(!s.empty()) {
		if(arr[j] != s.top()) {
			break;
		}
		answer.push_back('-');
		s.pop();
		j++;
	}
	
	
	
	if(!s.empty()) {
		cout << "NO" << '\n';
	}
	else {
		for(int i = 0; i < answer.size(); i++) {
			cout << answer[i] << '\n';
		}
	}
	
	return 0;
}

cout << endl; 와 cout << '\n'; 의 차이.

endl를 사용하는 것은 버퍼를 비우는 과정이 있어서 훨씬 느리다.

시간 초과가 뜨면 '\n'를 써보자.