글 읽기 - C++ 시간초과 어떻게 해결해야 할까요?? 도와주세요ㅜㅜ

qkrwldyd19 5년 전 0

삭제(B) 시, 처음부터 삭제될 문자 앞까지와 삭제될 문자 뒤부터 문자열의 끝까지를 각각 잘라서 이어 붙였고

삽입(P) 시, 처음부터 삽입될 위치 앞까지와 삽입될 문자, 삽입될 위치 뒤부터 끝까지를 이어 붙였습니다.

char* 형이 아니라 string형으로 입력받아서 오래 걸리는 걸까요?

아니면 substr 함수가 시간을 많이 잡아먹는 걸까요??

아니면 다른 이유가 있나요..?

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(void)
{
	string input;
	int operations = 0, cursor= 0;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> input;
	cursor = input.size();	// 최초 input string의 마지막에 커서가 위치

	cin >> operations;

	for (int i = 0; i < operations; i++)
	{
		char operation;
		cin >> operation;

		switch (operation)
		{
		case 'L':
			cursor = (--cursor < 0) ? 0 : cursor;	// 0보다 작아지면 0
			break;
		case 'D':
			cursor = (++cursor > input.size()) ? input.size() : cursor;		// size보다 커지면 size
			break;
		case 'B':
			if (cursor == 0)
				break;
			else {
				// 커서가 1 작아진 후
				cursor--;

				// input[0, cursor) + input(cursor, 끝]
				// 0 ~ 커서 전 + 원래 커서 후 ~ 끝
				input = (input.substr(0, cursor) + input.substr(cursor + 1, input.size()));
			}
			break;
		case 'P':
			char newWord;
			cin >> newWord;
			// input[0, cursor) + newWord + input[cursor, 끝]
			// 0 ~ 커서 전 + 새로운 문자 + 커서 후 ~ 끝
			input = (input.substr(0, cursor) + newWord + input.substr(cursor, input.size()));
			cursor++;
			break;
		default:
			break;
		}
	}
	cout << input << endl;

	return 0;
}

djm03178 5년 전 1

간단하게 예시를 들어서, 10만 자의 문자열에 substr + 문자 + substr를 하면 10만 1자의 문자열이 새로 만들어집니다. 이걸 50만 번 반복합니다. 버틸 수 있을까요?

지금은 하나의 string 문자열로도 통과하는 것이 가능은 하지만 (곧 안 되게끔 바뀌도록 요청을 했습니다), 이 문제는 원래 삽입 / 삭제를 O(1) 시간에 해야 하는 것이 정해입니다. string은 1차원 배열의 형태이기 때문에 중간에 원소를 껴넣거나 제거하는 것이 O(길이)의 시간이 걸립니다. 이 작업을 O(1)에 할 수 있도록 링크드 리스트를 사용하거나, 스택 2개를 쓰는 풀이를 생각해보세요.

qkrwldyd19 5년 전 0

감사합니다.

링크드리스트에서 현재 커서가 있는 위치 앞 쪽에서 삽입/삭제을 하면 간단히 해결되는군요.

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

문제

문제

출처

ICPC

C++ 시간초과 어떻게 해결해야 할까요?? 도와주세요ㅜㅜ

qkrwldyd19 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 1

qkrwldyd19 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말