글 읽기 - C++ 괄호의 값 시간초과??

sjsinju 5년 전 0

for/while을 과하게 도는것도 아닌데 시간초과가 나네요.

제출 후 시간이 나오는것 도 아니어서 디버깅이 너무 힘드네요..

어떤 부분이 시간초과의 원인일까요?? 답변 부탁드리겠습니다!! 미리 감사합니다.

#include <iostream>
#include <cstring>

using namespace std;

#define MAX_VAL 31

class Stack
{
public:
	void push(int x)
	{
		_data[++_top] = x;
	}
	int pop()
	{
		if (empty())
		{
			return -1;
		}
		else
		{
			return _data[_top--];
		}
	}
	int size()
	{
		return _top + 1;
	}
	int empty()
	{
		return _top == -1;
	}
	char top()
	{
		if (empty())
		{
			return -1;
		}
		else
		{
			return _data[_top];
		}
	}

private:
	int _data[MAX_VAL];
	int _top = -1;
};

inline int get(char c)
{
	if (c == '(') return -2;
	else if (c == ')') return -3;
	else if (c == '[') return -4;
	else if (c == ']') return -5;
	else if (c == '\0') return -6;

	return -10;
}

int main()
{
	Stack stack;

	char line[MAX_VAL];
	cin >> line;
	
	int i = 0;

	int ret_val = 0;

	while (line[i] != '\0')
	{
		if (line[i] == '(' || line[i] == '[')
		{
			stack.push(get(line[i]));
		}
		else if (line[i] == ')')
		{
			char poped = stack.pop();
			if (poped == get('('))
			{
				stack.push(2);
			}
			else if (poped == get('['))
			{
				cout << "0\n";
				return 0;
			}
			else
			{
				int sum = poped;
				while (stack.top() != get('('))
				{
					if (stack.top() == get('['))
					{
						cout << "0\n";
						return 0;
					}
					sum += stack.pop();
				}

				stack.pop(); // remove (
				sum *= 2;
				stack.push(sum);
			}
		}
		else if (line[i] == ']')
		{
			char poped = stack.pop();
			if (poped == get('['))
			{
				stack.push(3);
			}
			else if (poped == get('('))
			{
				cout << "0\n";
				return 0;
			}
			else
			{
				int sum = poped;
				while (stack.top() != get('['))
				{
					if (stack.top() == get('('))
					{
						cout << "0\n";
						return 0;
					}
					sum += stack.pop();
				}

				stack.pop(); // remove [
				sum *= 3;
				stack.push(sum);
			}
		}
		i++;
	}

	while (!stack.empty())
	{
		ret_val += stack.pop();
	}

	cout << ret_val << "\n";

	return 0;
}

djm03178 5년 전 0

) 하나만 입력해보세요.

sjsinju 5년 전 0

감사합니다. 완전 기본적인 것부터 접근해야 하는군요!!! ^^

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

문제

문제

출처

ICPC

C++ 괄호의 값 시간초과??

sjsinju 5년 전 0

djm03178 5년 전 0

sjsinju 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말