글 읽기 - [1152] C++ 정규 표현식을 이용한 풀이 메모리 초과 질문

sungje 3년 전 0

C++ 정규 표현식을 이용하여 문제를 풀어보려고 했는데

약 2~4% 정도에서 메모리 초과가 나오는데

정규 표현식으로 풀면 메모리 초과가 나오는 이유를 잘 모르겠어서 답변 부탁드립니다 ㅠㅠ

#include <iostream>
#include <regex>
#include <string>

using namespace std;

constexpr const char* REGEX = "([A-Za-z])\\w+";

int wordCount(string& str) {
	vector<string> word;
	
	regex re(REGEX);
	smatch match;

	auto start = sregex_iterator(str.begin(), str.end(), re);
	auto end = sregex_iterator();
	while (start != end) {
		word.push_back(start->str());
		++start;
	}

	return word.size();
}

void solve() {
	string str;
	getline(cin, str);
	cout << wordCount(str) << '\n';
}

int main() {
	solve();

	return 0;
}

phcdream 3년 전 1

[C++] 정규 표현식 - YoungJin Shin (jiniya.net)

한 가지 주의해야 할 점은 std::regex_match 함수의 경우 재귀 호출을 사용한다는 점이다. 따라서 정규 표현식에 따라서 문자열이 길면 스택 오버플로로 크래시가 발생할 수 있다.그 크기를 늘려주면 더 긴 문자열도 오류 없이 매치할 수 있다. 물론 너무 높게 설정하면 스택 오버플로로 크래시가 발생할 수 있다.

C++은 재귀호출을 사용하기때문에 재귀스택 오버플로우가 발생한다고 하네요. 다른언어에서는 어떻게 작동하는지는 잘 모르겠습니다.

아래 코드는 더 좋은 방법이 있을지도 모르겠지만, 일단 문자열을 잘라서 정규표현식 패턴 매치를 해보았습니다.

아래 코드의 DIV값(잘리는크기)에 따른 메모리와 실행시간차이입니다.

체점번호 메모리 시간

24206797 22728kb 92ms DIV 100000(10만)
24206789 5848kb 76ms DIV (10000(1만)
24206780 5064kb 76ms DIV 1000
24206764 5064kb 80ms DIV 100
24206752 5064kb 104ms DIV 10

#include <iostream>
//#define _REGEX_MAX_STACK_COUNT 2000000
#include <regex>
#include <string>
#include <fstream>

using namespace std;

#define DIV 100000

int wordCount(string& str) {

	string& s = str;

	std::regex words_regex("[^\\s]+");
	int len = str.length();
	int cnt = 0;
	for (int i = 0; i * DIV < len; i++)
	{
		std::sregex_iterator words_begin;
		if ((i + 1) * DIV < len)
		{
			words_begin =
				std::sregex_iterator(s.begin() + i * DIV, s.begin() + (i + 1) * DIV, words_regex);
		}
		else
		{
			words_begin =
				std::sregex_iterator(s.begin() + i * DIV, s.end(), words_regex);
		}
		auto words_end = std::sregex_iterator();
		cnt += distance(words_begin, words_end);
		if (i != 0)
		{
			if (s[(i)* DIV - 1] != ' ' && s[(i)* DIV] != ' ')
			{
				cnt--;
			}
		}
		//cout << distance(words_begin, words_end) << "\n";
	}

	return cnt;
}

void solve() {
	//ifstream cin;
	//cin.open("input.txt");
	string str;
	getline(cin, str);
	cout << wordCount(str) << '\n';
	//cin.close();
}

int main() {
	solve();
	//int n;
	//cin >> n;
	return 0;
}

phcdream 3년 전 1

그리고 vector에 string 넣는거 자체만으로도 메모리 초과가 납니다.

sungje 3년 전 1

빠른 답변 감사드립니다.

1. std::regex_match 함수는 재귀 호출을 사용

2. vector에 넣는 연산의 오버헤드 발생

다음부턴 조심해야겠네요!

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