글 읽기 - O(N)으로 풀었는데 시간초과가;;;

chkwon91 8년 전 0

읽어들인 문자열에서 글자 한 번씩만 검사하는 방법을 사용했습니다.

stack 개념을 사용하지 표준 라이브러리는 사용하지는 않았구요..

stack top에 있는 문자와 현재 문자가 동일하면 pop을 그렇지 않으면 push하고

문자열을 모두 읽고 나서 stack size가 0이면 가능한 단어로 판단했습니다.

단어를 한 번은 스캐닝 하도록 했습니다.. 그런데 시간초과가 뜨네요... 시간복잡도는 O(N)인데 시간초과가..

도대체 푸신분들은 어떻게 푸신건가요..? 단어를 다 훑지도 않고 푸신건가요? ㅠ

#include<cstdio>
#include<string.h>

char stack[100005];

int main(){
	int n, s_size, res=0;

	char s[100005];
	char cur;
	scanf("%d", &n);

	for(int i=0; i<n; i++){
		scanf("%s", s);
		s_size = 0;

		for(int piv=0; piv<strlen(s); piv++){
			cur = s[piv];
			if(s_size > (strlen(s)-piv))
				break;
			if(s_size==0)
				stack[s_size++]=cur;
			else if(stack[s_size-1]==cur)
				s_size--;
			else
				stack[s_size++]=cur;
			
		}
		if(s_size==0)
			res++;
	}

	printf("%d\n", res);

	return 0;
}

baekjoon 8년 전 7

for 안에 strlen(s)를 쓰면, 매번 strlen(s)를 구하게 됩니다.

즉 시간 복잡도는 strlen(s)의 제곱이 됩니다.

int len = strlen(s); 와 같이 변수로 따로 만들어주는 것이 좋을 것 같습니다.

chkwon91 8년 전 0

아 그렇군요! 그동안 몰랐습니다 ㅠㅠㅠ

AC 받았습니다 감사합니다!

bysu 6년 전 0

strlen의 시간 복잡도가 상수 시간이 아니었군요..
저도 하나 배워갑니다 ㅎ

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

문제

문제

출처

ICPC

O(N)으로 풀었는데 시간초과가;;;

chkwon91 8년 전 0

baekjoon 8년 전 7

chkwon91 8년 전 0

bysu 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말