글 읽기 - c++ 시간초과 도와주세요 ( _

jscb159 4년 전 0

안녕하세요!

c++로 벡터와 스택을 이용해서 스택 수열 문제를 풀었습니다.

제출 결과는 시간초과라고 나오더 라구요.

어떤 부분이 시간을 오래 잡아먹는지 알려주시면 감사드리겠습니다!

아니면 코드를 개선하기 위한 힌트라도 좋습니다!!

시간 내주셔서 글을 읽어주신 분들 모두 감사합니다 : )

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

bool check(vector <char> *op, int count, int *num, int *used);
void push(stack <int> *stack, int value, int *used);
void plusOP(vector <char> *op, int value, int *used);
void minusOP(vector <char> *op);

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

	int count, *num, *used;
	bool result;
	vector <char> op;

	cin >> count;

	num = new int[count];
	used = new int[count];

	for (int i = 0; i < count; i++) {
		cin >> num[i];
		used[i] = 0;
	}

	result = check(&op, count, num, used);

	if (result) {
		for (char c : op) {
			cout << c << '\n';
		}
	}
	else {
		cout << "NO\n";
	}
}

bool check(vector <char>* op, int count, int* num, int* used) {
	stack <int> stack;

	for (int i = 0; i < count; i++) {
		if (stack.empty()) {
			push(&stack, num[i], used);
			plusOP(op, num[i], used);
			stack.pop();
			minusOP(op);
		}
		else if (num[i] > stack.top()) {
			push(&stack, num[i], used);
			plusOP(op, num[i], used);
			stack.pop();
			minusOP(op);
		}
		else if (num[i] == stack.top()) {
			stack.pop();
			minusOP(op);
		}
		else {
			return false;
		}
	}

	return true;
}

void push(stack <int>* stack, int value, int* used) {

	for (int i = 0; i < value; i++) {
		if (used[i] != 0) {
			continue;
		}
		else {
			(*stack).push(i + 1);
		}
	}	
}

void plusOP(vector <char>* op, int value, int* used) {

	for (int i = 0; i < value; i++) {
		if (used[i] == 0) {
			(*op).push_back('+');
			used[i]++;
		}
	}
}

void minusOP(vector <char>* op) {

	(*op).push_back('-');

}

skysign 3년 전 1

벡터를 사용하지 않고, 2개의 스택만으로 문제를 푸는 것이 조금더 간결해서 좋을 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 시간초과 도와주세요 ( _ _ )

jscb159 4년 전 0

skysign 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말