글 읽기 - 시간초과 질문있습니다

jmingrove21 4년 전 0

strlen도 많이 줄였는데 시간 초과가 납니다...이유를 모르겠습니다ㅜㅜ

#include <iostream>
#include <string>
using namespace std;
const int max_strlen = 100000;
const int max_opercount = 500000;
/*
Rules

- L		커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
- D		커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
- B		커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
		삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
- P$	$라는 문자를 커서 왼쪽에 추가함
**/

int main(void){
	char str[max_strlen] = {};
	int number = 0;
	cin >> str;
	int curser_po = strlen(str)+1;
	cin >> number;

	for (int i = 0; i < number; i++){
		char ch = NULL;
		cin >> ch;
		if (ch == 'L'){
			if (curser_po == 1){
				continue;
			}
			else{
				curser_po--;
			}
		}
		else if (ch == 'D'){
			int len = strlen(str);
			if (curser_po == len+ 1){
				continue;
			}
			else{
				curser_po++;
			}
		}
		else if (ch == 'B'){
			if (curser_po == 1){
				continue;
			}
			else{
				int len = strlen(str);
				for (int j = curser_po-1; j <len; j++){
					str[j - 1] = str[j];
				}
				curser_po--;
				str[len - 1] = NULL;
			}
		}
		else if (ch == 'P'){
			char input = NULL;
			cin >> input;
			int len = strlen(str);
			for (int j =len-1; j >= curser_po-1; j--){
				str[j+1] = str[j];
			}
			str[curser_po - 1] = input;
			curser_po++;
		}

	}
	printf("%s\n", str);

	return 0;
}

djm03178 4년 전 0

이유는 이 코드가 O(n^2)이기 때문입니다. 어떤 연산을 하나 할 때마다 모든 내용을 뒤로 밀거나 앞으로 당겨오는 작업을 하지 않아야 합니다.

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

문제

문제

출처

ICPC

시간초과 질문있습니다

jmingrove21 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말