글 읽기 - 시간 초과가 나는 이유..?

minjun623 6년 전 0

R, D 입력시에 해결 하는게 문제가 바라는 바인거 같은데, 스텍 두개를 사용해서 O(n)을 구현 한거 같은데......

어디가 문제일까요?

#include <cstdio>
#include <string>
#include <iostream>
#include <stack>

using namespace std;

int main(){
	int trap; scanf("%d", &trap);
	for (int i = 0; i < trap; ++i){
		string string_code;
		string string_arr;
		cin >> string_code;			//RDD
		int arr_size; scanf ("%d", &arr_size);	//4
		cin >> string_arr;			//[1,2,3,4]

		stack<int> input;
		stack<int> trans;
		//stack에 역순으로 입력 [4, 3, 2, 1].
		int x = 0, y = 1;
		for (int i = string_arr.size()-2; i >= 0; --i){
			if (string_arr[i] == ',' || string_arr[i] == '['){
				input.push(x);
				x = 0, y = 1;
			}
			else {
				x += y*(string_arr[i]-48);
				y *= 10;
			}
		}

		//R 입력시 stack 이동.
		//D 입력시 stack 가장 위에 있는 수 pop.
		int check = 0, error = 0; //채워진 스택이 어디인지 체크, 에러의 유무 체크.
		int string_code_size = string_code.size();
		for (int i = 0; i < string_code_size; ++i){
			if (string_code[i] == 'R'){
				if (check){	//trans -> input
					for (int i = 0; i < arr_size; ++i){
						input.push(trans.top());
						trans.pop();
					}
				}
				else{	//input -> trans
					for (int i = 0; i < arr_size; ++i){
						trans.push(input.top());
						input.pop();
					}
				}
				check = !check;
			}

			else {	//string_code[i] == 'D'
				if(arr_size-- == 0){
					error = 1;
					break;
				}
				else if (check){	//trans pop
					trans.pop();
				}
				else {	//input pop
					input.pop();
				}
			}
		}

		//출력.
		if (error) printf("error\n");
		else if (check){	//trans 출력
			printf("[");
			for (int i = 0; i < arr_size-1; ++i){
				printf("%d,", trans.top());
				trans.pop();
			}
			if (!trans.empty()) printf("%d", trans.top());
			printf("]\n");
		}
		else {	//input 출력
			printf("[");
			for (int i = 0; i < arr_size-1; ++i){
				printf("%d,", input.top());
				input.pop();
			}
			if (!input.empty()) printf("%d", input.top());
			printf("]\n");
		}
	}
	return 0;
}

3587jjh 6년 전 0

R이 나올때 직접 뒤집어보지 않고 결과를 유추해야해요

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

문제

문제

출처

ICPC

시간 초과가 나는 이유..?

minjun623 6년 전 0

3587jjh 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말