글 읽기 - 5430번 문제 시간초과 질문입니다.

gogo392539 6년 전 0

이렇게 코드를 작성했는데, 시간초과가 나오네요... 이 방식 말고 다른 방식을 써야 할까요...?

#include <iostream>
#include <algorithm>
#include <deque>
#include <string>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	int T;			//test case의 수
	string strP;	//수행할 함수
	int n;			//배열에 들어있는 수의 개수
	deque<int> x;	//배열에 들어있는 수
	int tempX = 0;
	char temp;
	int result;
	int plen;

	//cin >> T;
	scanf_s("%d", &T);

	for (int i = 0; i < T; i++) {
		cin >> strP;
		plen = strP.length();

		//cin >> n;
		scanf_s("%d", &n);

		result = 1;
		while (1) {
			temp = getchar();
			if (temp >= '0' && temp <= '9') {
				tempX *= 10;
				tempX += temp - '0';
			}
			else if (temp == ',') {
				x.push_back(tempX);
				tempX = 0;
			}
			else if (temp == ']') {
				if (tempX != 0) {
					x.push_back(tempX);
				}
				tempX = 0;
				break;
			}
		}

		for (int i = 0; i < plen; i++) {
			switch (strP[i])
			{
			case 'R':
				reverse(x.begin(), x.end());
				break;
			case 'D':
				if (x.empty()) {
					result = 0;
					break;
				}
				else {
					x.pop_front();
				}
				break;
			}
		}

		int len = x.size();

		if (result == 1) {
			//cout << "[";
			printf("[");
			for (int i = 0; i < len; i++) {
				//cout << x.front();
				printf("%d", x.front());
				x.pop_front();
				if (!x.empty()) {
					//cout << ",";
					printf(",");
				}
			}
			//cout << "]" << endl;
			printf("]\n");
		}
		else {
			//cout << "error" << endl;
			printf("error\n");
		}
		x.clear();
		
	}

	return 0;
}

djm03178 6년 전 1

reverse 함수는 길이만큼의 시간이 걸리기 때문에 자주 뒤집으면 시간이 매우 오래 걸립니다. 상수 시간에 뒤집기를 표현해야 합니다.

gogo392539 6년 전 0

감사합니다!

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

문제

문제

출처

ICPC

5430번 문제 시간초과 질문입니다.

gogo392539 6년 전 0

djm03178 6년 전 1

gogo392539 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말