[BaekJoon] 백준 1874번 스택 수열

백준 1874번 스택 수열

 

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

 

 

내코드

 

문제 풀이

 

(1-1) max값(현재 입력값중 최대값, 초기값은 0)이 입력값 보다 작으면 (max+1) ~ 입력값까지 push해준다.

(1-2) 크거나 같은 경우 pop을 해줘야 하므로 스택의 top이 입력값과 같은지 체크한다. 같지 않을 경우 NO를 출력하며 프로그램 종료.

(2) pop을 해준다.

(3) max값이 입력값보다 작으면 max값을 입력값으로 초기화 해준다.

 

 

주의점

 

- endl 는 버퍼를 비우기 때문에 느림. 시간초과가 남. "\n"을 써주자.

 

#include <iostream> 
#include <string>

using namespace std;

int stack[100000];
int top = 0;
char * result;
int pointer = 0;

void push(int num) {
	stack[top++] = num;
	result[pointer++] = '+';
}

int pop() {
	result[pointer++] = '-';
	return stack[--top];
}

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

	int n = 0;
	cin >> n;
	result = new char[n];

	int max = 0;
	while(n--) {
		int tmp = 0;
		cin >> tmp;

		if (max < tmp) {
			for (int i = max + 1; i <= tmp; i++) {
				push(i);
			}
		}
		else {
			if (stack[top-1] != tmp) {
				cout << "NO" << "\n";
				return 0;
			}
		}
		pop();
		if (max < tmp) max = tmp;
	}

	for (int i = 0; i < pointer; i++) {
		cout << result[i] << "\n";
	}

	return 0;
}