글 읽기 - 계속 시간 초과가 나오는데 어떻게 하면 연산속도를 보다 빠르게 할 수 있을까요

justinohr 6년 전 0

시간 단축을 위해 왠만한 연산자를 c++ 함수말고 c함수로 고쳤는데도 계속 시간초과가 나오네요.

어떻게 고치면 괜찮아질까요?

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

using namespace std;
char arr[100001];
deque<int> num;
int main() {
	int T, l, i, j, r, n;
	char c;
	int size;
	scanf("%d", &T);
	for (i = 0; i < T; i++) {
		r = 0;
		scanf("%s", arr);
		scanf("%d", &l);
		getchar(); getchar();
		for (j = 0; j < l; j++) {
			n = 0;
			while (c = getchar(), c != ',' &&  c!= ']') {
				n *= 10;
				n += c - '0';
			}
			num.push_back(n);
		}
		for (j = 0; j < strlen(arr); j++) {
			if (arr[j] == 'R')
				r++;
			else {
				if (r % 2 == 0) {
					if (num.empty()) {
						printf("error\n");
						break;
					}
					else num.pop_front();
				}
				else {
					if (num.empty()) {
						printf("error\n");
						break;
					}
					else num.pop_back();
				}
			}
		}
		if (!num.empty()) {
			size = num.size();
			putchar('[');
			if (r % 2 == 0) {
				for (j = 0; j < size - 1; ++j) {
					printf("%d,", num.front());
					num.pop_front();
				}
				printf("%d]\n", num.front());
			}
			else {
				for (j = 0; j < size - 1; ++j) {
					printf("%d,", num.back());
					num.pop_back();
				}
				printf("%d]\n", num.back());
			}
		}
		num.clear();
	}
	return 0;
}

yukariko 6년 전 2

for (j = 0; j < strlen(arr); j++) {

이 코드가 문제인것 같습니다.

위 코드는 O(N)을 의도한 코드이지만, O(N^2)으로 동작하게 됩니다.

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

문제

문제

출처

ICPC

계속 시간 초과가 나오는데 어떻게 하면 연산속도를 보다 빠르게 할 수 있을까요

justinohr 6년 전 0

yukariko 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말