글 읽기 - 왜 50%에서 시간초과가 나는지 도무지 모르겠네요

wiz9243 6년 전 0

다른 질문들도 보고 여러 풀이도 봤는데 제 코드에서 도무지 시간초과가 날 만한 것을 못찾겠습니다 ㅜ 고수님들 도와주세요

#include<iostream>
#include<deque>
#include<stdio.h>	
#include<string.h>

using namespace std;

char v[100005];
deque <int> dq;

int main() {
	int T, su, temp, flag;

	scanf("%d", &T);
	for ( int k = 0; k < T; k++ ) {
		flag = -1;

		cin.ignore();
		scanf("%s", v);
		scanf("%d", &su);
		cin.ignore(); 
		if ( su != 0 ) {
			getchar();
			for ( int i = 0; i < su; i++ ) {
				scanf("%d", &temp);
				dq.push_back(temp);
				getchar();
			}
		}
		else {
			getchar();
			getchar();
		}
		for ( int i = 0; i < strlen(v); i++ ) {
			if ( v[i] == 'R' ) {
				flag *= -1;
			}
			else {
				if ( dq.empty() == 0 ) {
					if ( flag == -1 ) {
						dq.pop_front();
					}
					else {
						dq.pop_back();
					}
				}
				else {
					printf("error\n");
					temp = 10000;
					break;
				}
			}
				
		}
		
		if ( dq.empty() == 0 ) {
			if ( flag == -1 ) {
				printf("[");
				while ( !dq.empty() ) {
					printf("%d", dq.front());
					dq.pop_front();
					if ( !dq.empty() )printf(",");
				}
				printf("]\n");
			}
			else {
				printf("[");
				while ( !dq.empty() ) {
					printf("%d", dq.back());
					dq.pop_back();
					if ( !dq.empty() )printf(",");
				}
				printf("]\n");
			}
		}
		else if ( dq.empty() == 1 && temp != 10000 ) {
			printf("[]\n");

		}
			
		dq.clear();
		
	}

	return 0;
}

kdk8361 6년 전 0

확실하진 않지만 deque를 pop하면서 메모리 관리때문에 시간초과가 나는 것 같습니다. 다른방법을 한번 생각해보세요

kdk8361 6년 전 0

아 죄송합니다. deque때문이 아니라 34번 줄에 있는 strlen 때문입니다. 문자열의 길이를 체크하는 함수는 O(n)이 걸리는데 for문의 조건체크하는 부분에 들어가게 되면 for문이 한번 돌 때마다 저 strlen을 돌리게 됩니다. 따라서 다른 변수에 길이를 저장하시고 사용하시면 TLE는 안나올 것 같습니다.

wiz9243 6년 전 0

감사합니당!

wiz9243 6년 전 0

strlen를 다른 변수에 넣기만 했을 뿐인데 처음부터 틀렸다고 나오네요ㅜㅜ

kdk8361 6년 전 1

반례입니다

1
R
0
[]

ans : []

wiz9243 6년 전 0

진짜 대단하시네요! 해결됬습니다. 도와주셔서 정말 감사합니다.

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

문제

문제

출처

ICPC

왜 50%에서 시간초과가 나는지 도무지 모르겠네요

wiz9243 6년 전 0

kdk8361 6년 전 0

kdk8361 6년 전 0

wiz9243 6년 전 0

wiz9243 6년 전 0

kdk8361 6년 전 1

wiz9243 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말