백준 1874번 : 스택 수열

문제 링크 : www.acmicpc.net/problem/1874

풀이에 참고한 링크 : www.acmicpc.net/board/view/52749

내 풀이 (2020.12.18.) :

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
	stack<int> stack;
	int n; cin >> n;

	vector<int> target_list;
	int target_index = 0;

	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		target_list.push_back(num);
	}

	int input = 1;
	int max_num = 0;

	vector<char> answer_list;
	bool flag = false;

	while (target_index < target_list.size()) {
		int target_num = target_list.at(target_index);
		if (target_num > max_num) {
			while (target_num >= input) {
				stack.push(input);
				answer_list.push_back('+');
				input++;
			}
			stack.pop();
			answer_list.push_back('-');
			max_num = target_num;
		}
		else {
			int top = stack.top();
			if (target_num == top) {
				stack.pop();
				answer_list.push_back('-');
			}
			else {
				flag = true;
				break;
			}
		}
		target_index++;
	}
	if (flag) cout << "NO" << endl;
	else {
		for (int i = 0; i < answer_list.size(); i++) {
			cout << answer_list.at(i) << endl;
		}
	}

	return 0;
}

결과 : 시간 초과

원인 :

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

위의 코드를 쓰면 cin와 cout의 성능이 좋아진다.

그런데 저 코드를 써도 시간 초과가 났다.

찾아보니, endl가 특히 성능을 더욱 떨어뜨린다고 했다.

그래서 endl 대신 \n를 썼지만, 그래도 시간 초과가 났다.

결국 printf로 바꾸니 그제서야 시간 초과가 나지 않았다.

그냥 앞으로는 무조건 printf를 쓰도록 하자.

(아, 참고로 실험을 해보니 scanf보다 cin.tie(NULL)을 적용한 cin이 미세하게 더 빨랐다.)

---

내 풀이2 (2020.12.18.) :

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	stack<int> stack;
	int n; cin >> n;

	vector<int> target_list;
	int target_index = 0;

	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		target_list.push_back(num);
	}

	int input = 1;
	int max_num = 0;

	vector<char> answer_list;
	bool flag = false;

	while (target_index < target_list.size()) {
		int target_num = target_list.at(target_index);
		if (target_num > max_num) {
			while (target_num >= input) {
				stack.push(input);
				answer_list.push_back('+');
				input++;
			}
			stack.pop();
			answer_list.push_back('-');
			max_num = target_num;
		}
		else {
			int top = stack.top();
			if (target_num == top) {
				stack.pop();
				answer_list.push_back('-');
			}
			else {
				flag = true;
				break;
			}
		}
		target_index++;
	}

	if (flag) printf("NO");
	else {
		for (int i = 0; i < answer_list.size(); i++) {
			printf("%c\n", answer_list.at(i));
		}
	}

	return 0;
}

결과 : 성공

풀이 방법 :

  순서도를 그려서 해결했다.