#1874 스택 수열

# 문제

# 입력 및 출력

# 풀이

롤 방송 틀어놓고 풀어서 그런지 집중이 안돼서 3일을 붙잡고있었던 것 같다ㅋㅋㅋ

오늘 각잡고 앉아서 풀었는데 나름 쉽게 풀린 것 같다

대충 쓸 변수랑 돌아가는 방식을 단계별로 나눠서 손으로 작동시켜봤다

처음에 cin, cout, endl을 썼더니 출력이 너무 많아져서 그런지 시간초과가 떴다

아무리봐도 알고리즘엔 문제가 없어보이는데 시간 초과가 뜨길래 저번처럼 입출력에서 문제인가 싶어서

printf, scanf로 바꾸고 endl은 \n으로 바꿔서 돌렸더니 돌아가더라ㅋㅋ

 

#pragma warning (disable:4996)
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
stack<int> s;
vector<char> op;
int inp[100000];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &inp[i]);
	}
	int index = 0, num = 1;
	while (index < n) {
		if (inp[index] >= num) {
			s.push(num);
			op.push_back('+');
			num++;
		}
		else {
			if (s.top() == inp[index]) {
				while (s.top() == inp[index]) {
					s.pop();
					op.push_back('-');
					index++;
					if (s.empty()) break;
				}
			}
			else {
				printf("NO\n");
				return 0;
			}
		}
	}
	while (!op.empty()) {
		printf("%c \n", op.front());
		op.erase(op.begin());
	}
}

 

이게 내가 작성한 코든데 다른 사람 코드를 보니 더 줄일 수 있을 것 같아서 바꿔봤다

조건문을 좀 간단하게 바꿨음

#pragma warning (disable:4996)
#include <iostream>
#include <stack>
#include <vector>

using namespace std;
stack<int> s;
vector<char> op;

int main() {
	int n, index = 0, num = 1, inp;
	scanf("%d", &n);
	while (index < n) {
		scanf("%d", &inp);
		while (inp >= num) {
			s.push(num);
			op.push_back('+');
			num++;
		}
		if (s.top() == inp) {
			s.pop();
			op.push_back('-');
			index++;
		}
		else {
			printf("NO\n");
			return 0;
		}
	}
	while (!op.empty()) {
		printf("%c\n", op.front());
		op.erase(op.begin());
	}
}

num이랑 inp값이 같을 때 까지 push하기 때문에 s.top이 inp과 다르다면

수열이 만들어질수가 없기 때문에 바로 NO를 출력해준다

 

여기서 또 다른 사람 코드를 봤는데ㅋㅋ

실행 시간이 나는 거의 700ms인데 어떤 사람은 같은 c++이라도 16ms이정도밖에 안나오길래 코드를 구경을 좀 했다

나는 +, - 출력을 위해 vector를 썼는데 그 사람은 string을 써서 그냥 +, -를 문자열에 붙이는 방식으로 출력하더라

그래서 여기서 수정을 좀 더 했다

#pragma warning (disable:4996)
#include <iostream>
#include <stack>
#include <string>

using namespace std;
stack<int> s;
string op;

int main() {
	int n, index = 0, num = 1, inp;
	scanf("%d", &n);
	while (index < n) {
		scanf("%d", &inp);
		while (inp >= num) {
			s.push(num);
			op += "+\n";
			num++;
		}
		if (s.top() == inp) {
			s.pop();
			op += "-\n";
			index++;
		}
		else {
			printf("NO\n");
			return 0;
		}
	}
	cout << op;
}

코드도 확실히 줄고 실행시간도 45배정도 빨라짐ㅋㅋ