5430 시간초과부분 질문있습니다.

작성한 질문수 15

0

안녕하세요 선용님 ㅎㅎ

		/*str_arr.erase(0, sizeof('['));
		str_arr.erase(str_arr.size()-1, sizeof(']'));
		while (str_arr.size())
		{
			auto iter = str_arr.find(',');
			if (iter == str_arr.npos)
			{
				arr.push_back(std::stoi(str_arr));
				str_arr.clear();
				break;
			}
			arr.push_back(std::stoi(str_arr.substr(0, iter)));
			str_arr.erase(0, iter+1);
		}*/

지금 링크를 타고 드가면 맞았습니다가 뜨는데 이부분을 넣으면 시간초과가 걸린다는 말씀이시죠?

먼저 이렇게 생각하셔야 합니다.

효율적인 코드 ? >> 생각이 안남 >> 일단 맞는 로직 >> 시간초과 >> 효율적인 코드

이런 흐름으로 문제를 푸셔야 합니다. 처음부터 효율적인 코드를 생각할 수는 있으나 그렇지 않을 수도 있으니 일단은 로직상 맞는 로직으로 구현하셔야 합니다.

이 문제 같은 경우 저 부분이 시간초과가 나는 것이지만 다른 문제는 또 아닐 수도 있기 때문입니다.

시간복잡도 분석은 다음과 같습니다.

auto iter = str_arr.find(',');

find는 O(N)의 시간복잡도를 가집니다.

arr.push_back(std::stoi(str_arr));

stoi는 O(1)의 시간복잡도를 가집니다. (str.size()가 정확하긴 합니다.)

str_arr.substr(0, iter)

substr는 O(N)의 시간복잡도를 가집니다.

제 생각에는 find, substr 때문에 시간초과가 나는 것 같습니다.

감사합니다.

0

안녕하세요, 인프런 AI 인턴이에요. 5430 문제 코드를 보았는데요, 시간 초과가 발생하는 부분에 대해서 문의하셨는데요, find 및 substr 함수의 사용으로 인해 시간 초과가 발생하는 것은 가능성이 있습니다.

일반적으로 find 함수는 문자열을 탐색하기 위해 사용되는데, 문자열 전체를 탐색해야 하므로 시간 복잡도가 O(N)이 되어 시간 초과의 원인이 될 수 있습니다. substr 함수는 주어진 인덱스 범위의 문자열을 복사하는 작업을 수행하는데, 복사 작업 자체가 시간이 많이 소요될 수 있어 시간 초과를 발생시킬 수 있습니다. 또한 stoi 함수도 문자열을 정수로 변환하는 작업을 수행하는데, 이 작업 역시 시간이 소요될 수 있습니다.

따라서, 이러한 함수들을 반복문 안에서 여러 번 호출하게 되면 시간 복잡도가 증가하여 시간 초과가 발생할 수 있습니다. 따라서, 이러한 함수들의 호출 횟수를 최소화하는 등의 최적화 작업을 통해 시간 복잡도를 개선하면 시간 초과를 해결할 수 있을 것입니다.

그러나, 정확한 원인을 파악하기 위해서는 코드를 자세히 분석해야 하므로, 코드 전체를 보시고 시간 초과가 발생하는 부분을 판단해보시는 것이 좋을 것 같습니다.