글 읽기 - 시간초과나는데 어떻게 해결해야할까요??

codmsdl21 5년 전 0

다른 반례들이랑 테스트케이스 다 맞는데

시간초과가 납니다 ㅜㅜ

30개짜리 입력도 넣어봤는데 잘 출력되구요...

for문도 한 번밖에 안도는데 뭐가 문제일까요..?

#include<cstdio>
#include<stack>
using namespace std;

char arr[30];
int cnt[30];
stack<char> st;

int main(void) {

	char tmp;
	int n = 0;


	while (1) {
		tmp = getchar();
		if (tmp == '\n')	break;
		arr[n++] = tmp;
	}

	for (int i = 0; i < n; i++) cnt[i] = 1;

	int x = 1;

	if (arr[0] == ']' || arr[0] == ')') {
		printf("0\n");
		return 0;
	}
	else if (arr[0] == '(') {
		x *= 2;
		cnt[0] = 2;
	}
	else if (arr[0] == '[') {
		x *= 3;
		cnt[0] = 3;
	}

	st.push(arr[0]);

	int ans = 0;

	for (int i = 1; i < n; i++) {
		if (arr[i] == '(') {
			st.push(arr[i]);
			x *= 2;
			cnt[i] = x;
		}
		else if (arr[i] == '[') {	
			st.push(arr[i]);
			x *= 3;
			cnt[i] = x;
		}
		else{
			if (st.empty()) {
				printf("0\n");
				return 0;
			}

			if (arr[i] == ']' && st.top() == '[') {
				x /= 3;
				cnt[i] = cnt[i - 1];
				st.pop();
			}
			else if (arr[i] == ')' && st.top() == '(') {
				x /= 2;
				cnt[i] = cnt[i - 1];
				st.pop();
			}
			else {
				printf("0\n");
				return 0;
			}
			if (i + 1 < n && (arr[i + 1] == '(' || arr[i + 1] == '[')) {
				ans += cnt[i];
			}
		}
		
	}

	
	if (x > 1) printf("0\n");
	else {
		ans += cnt[n - 1];
		printf("%d\n", ans);
	}

	return 0;
}

zxcvber 5년 전 3

17번째 줄에서 입력의 끝을 개행문자로 받으셨는데 입력에서 개행문자가 주어지지 않을수도 있습니다.

그 경우에는 while 문에서 계속 돌아서 시간초과가 나게 됩니다.

codmsdl21 5년 전 0

헐 ㅜㅜㅜㅜ 감사합니다!!!!!!

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

문제

문제

출처

ICPC

시간초과나는데 어떻게 해결해야할까요??

codmsdl21 5년 전 0

zxcvber 5년 전 3

codmsdl21 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말