글 읽기 - 시간초과가 뜨는데요..

wnsrnek3 7년 전 0

생각한대로 잘라서 잘라서 붙여넣듯이 짜보았는데요..

결과는 잘나오는거 같은데, 결국 시간초과가 떠버리고마네요.

append는 많~~이 느린가요? 느리다면 어떤점에서 느린걸까요?

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

int main() {
	char strt[600001]; scanf("%s", strt);
	string str(strt);
	int cursor = str.length();
	int n;  scanf("%d", &n);
	string temp;
	for (; n--;) {
		temp = "";
		string inst; cin >> inst;		
		if (inst.compare("L")==0) {
			if (cursor > 0) cursor--;
		}
		if (inst.compare("D")==0) {
			if (cursor < str.length()) cursor++;
		}
		if (inst.compare("B") == 0) {
			temp.append(str.substr(0, cursor - 1));
			temp.append(str.substr(cursor, str.length() - cursor));
			if (cursor > 0) cursor--;
			str = temp;
		}
		
		if (inst.compare("P")==0) {
			string ch; cin >> ch;
			temp.append(str.substr(0, cursor));
			temp.append(ch);
			temp.append(str.substr(cursor, str.length()-cursor));
			 cursor++;
			str = temp;
		}
	}
	cout << str;
	return 0;

}

wnsrnek3 7년 전 0

append하면서 O(n) 그게 문자열길이만큼이면 O(n^2), 최대 60만*60만이 되네요..

링크드리스트로 구현하는게 좋을듯.

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

문제

문제

출처

ICPC

시간초과가 뜨는데요..

wnsrnek3 7년 전 0

wnsrnek3 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말