글 읽기 - 시간 초과좀 도와주시면 감사하겠습니다. (소스코드 수정합니다)

dydsj0920 6년 전 0

강의에서 배운것처럼 Stack을 왼쪽과 오른쪽으로 나누어서

작성하였는데 시간초과가 뜨네요.. 어떻게 수정해야 할까요?

//검열
#include "stdafx.h"
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

stack<char> s_left;
stack<char> s_right;

string A, T, A_R;

int pos_l;
int pos_r;

string temp_l;
string temp_r;

string ans;

void GoStackR();

void GoStackL()
{
	for (int i = pos_l; i <= pos_r; i++) {
		s_left.push(T[i]);
		temp_l += T[i];
		if (temp_l.find(A) != string::npos) {
			for (int i = 0; i < A.size(); i++) {
				s_left.pop();
			}
			pos_l = i+1;
			temp_l.resize(temp_l.size() - A.size());
			GoStackR();
			return;
		}
	}
}

void GoStackR()
{
	for (int i = pos_r; i >= pos_l; i--) {
		s_right.push(T[i]);
		temp_r += T[i];
		if (temp_r.find(A_R) != string::npos) {
			for (int i = 0; i < A_R.size(); i++) {
				s_right.pop();
			}
			pos_r = i-1;
			temp_r.resize(temp_r.size() - A_R.size());
			GoStackL();
			return;
		}
	}
}

void GoFinal()
{
	//left스택에 있는것을 right스택으로 옮겨주면서 A확인
	while (!s_left.empty()) {
		s_right.push(s_left.top());
		s_left.pop();
		temp_r += s_right.top();
		if (temp_r.find(A_R) != string::npos) {
			for (int i = 0; i < A_R.size(); i++) {
				s_right.pop();
			}
			temp_r.resize(temp_r.size() - A_R.size());
		}
	}
	while (!s_right.empty()) {
		ans += s_right.top();
		s_right.pop();
	}
}

int main()
{

	cin >> A >> T;

	A_R = A;
	reverse(A_R.begin(), A_R.end());

	pos_l = 0;
	pos_r = T.size() - 1;

	GoStackL();
	GoFinal();

	cout << ans << '\n';

}

cx8achim 5년 전 0

제 생각인데 저 string.find 함수가 o(n)이라서 결과적으로 o(n^2) 이라서 스택을 사용한게 의미없는거같아요

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

문제

문제

출처

ICPC

시간 초과좀 도와주시면 감사하겠습니다. (소스코드 수정합니다)

dydsj0920 6년 전 0

cx8achim 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말