글 읽기 - 5397 키로거 시간초과 질문!

dreammusic23 8년 전 0

-,<,>가 아니면 모두 push해주고,

-일때 pop해주고,

<이면 다른 스택에 저장해서 나중에 붙이게 하고,

>이면 다른 스택에 있는 것을 원래 스택으로 넣었습니다!

물론 잘 되는데...

문제는 시간초과가 뜹니다... ㅠㅠㅠㅠㅠ

대체 어디가 문제고, 어떻게 해야 시간초과가 뜨지 않을까요?

#include "stdio.h"
#include "string.h"
char stack[1000005]={0};
char stack1[1000005]={0};
char string[1000005]={0};
int top=0,top1=0,top2=0;
void push(char x){
	stack[++top]=x;
	top1+=1;
}
void push1(char y){
	stack[++top]=stack1[top2];
	stack1[top2]=0;
	top1+=1;
}
void pop(){
	stack[top]=0;
}
void pop1(char z){
	stack1[++top2]=stack[top];
	stack[top]=0;
}
int main(){
	int input,i,j;
	scanf("%d",&input);
	for(i=0;i<input;i++){
		scanf("%s",string);
		for(j=0;j<=strlen(string);j++){
			if(string[j]=='<'){
				if(top>0){
					if(string[j-1]=='<'){
						top-=1;
						top1-=1;
						pop1(stack[top]);
					}
					else
						pop1(stack[top]);
				}
			}
			else if(string[j]=='>'){
				push1(stack1[top2]);
			}
			else if(string[j]=='-'){
				if(top>0){
					if(string[j-1]=='-'){
						top-=1;
						top1-=1;
						pop();
					}
					else
						pop();
				}
			}
			else
				push(string[j]);
		}
		for(j=0;j<=top1;j++){
			printf("%c",stack[j]);
		}
		for(j=top2;j>0;j--){
			printf("%c",stack1[j]);
		}
		printf("\n");
		memset(string,0,sizeof(strlen(string)));
		memset(stack,0,sizeof(top1));
		memset(stack1,0,sizeof(top2));
		top2=0;
		top1=0;
		top=0;
	}
	return 0;
}

csehydrogen 8년 전 0

for(j=0;j<=strlen(string);j++)

매 루프마다 strlen을 계산하게 됩니다. 다른 변수에 값을 넣어두시고 사용하는게 좋아요.

csehydrogen 8년 전 0

string이 문자열 object였다면 string.length() 같은 함수가 상수시간안에 수행되겠지만

strlen은 단순히 앞에서부터 NULL이 나올때까지 보면서 갯수를 세는 함수이기 때문에 수행시간이 문자열 길이에 비례합니다.

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

문제

문제

출처

ICPC

5397 키로거 시간초과 질문!

dreammusic23 8년 전 0

csehydrogen 8년 전 0

csehydrogen 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말