글 읽기 - string 질문이요!!

pig07911 3년 전 0

위에꺼가 맞은거고 아래꺼가 틀린코드인데 둘의 차이는 마지막에

ans+=st.top() 랑 ans=ans+st.top() 이거인데 ans+=st.top()는 맞고 ans=ans+st.top()이거는 시간초과나는데 이유좀 알려주세요ㅠㅠ

/////////////////정답코드///////////////////////////
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s, bomb;
	cin >> s >> bomb;
	stack<char> st;
	int bomblen = bomb.length();
	for (int i = 0; i < s.length(); i++)
	{
		st.push(s.at(i));
		if (st.size() >= bomblen)
		{
			stack<char> tmp;
			bool flag = 0;
			for (int j = bomblen - 1; j >= 0; j--)
			{
				if (st.top() != bomb.at(j))
				{
					flag = 1;
					break;
				}
				else if (st.top() == bomb.at(j))
				{
					tmp.push(st.top());
					st.pop();
				}
			}
			if (flag == 1)
			{
				while (tmp.empty() == 0)
				{
					st.push(tmp.top());
					tmp.pop();
				}
			}
		}
	}
	string ans;
	if (st.empty() == 1)
	{
		cout << "FRULA";
	}
	else
	{
		while (st.empty() == 0)
		{
			ans+=st.top();
			st.pop();
		}
		for (int i = ans.length() - 1; i >= 0; i--)
		{
			cout << ans.at(i);
		}
	}
}
///////////////////오답코드///////////////////////////////
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s, bomb;
	cin >> s >> bomb;
	stack<char> st;
	int bomblen = bomb.length();
	for (int i = 0; i < s.length(); i++)
	{
		st.push(s.at(i));
		if (st.size() >= bomblen)
		{
			stack<char> tmp;
			bool flag = 0;
			for (int j = bomblen - 1; j >= 0; j--)
			{
				if (st.top() != bomb.at(j))
				{
					flag = 1;
					break;
				}
				else if (st.top() == bomb.at(j))
				{
					tmp.push(st.top());
					st.pop();
				}
			}
			if (flag == 1)
			{
				while (tmp.empty() == 0)
				{
					st.push(tmp.top());
					tmp.pop();
				}
			}
		}
	}
	string ans;
	if (st.empty() == 1)
	{
		cout << "FRULA";
	}
	else
	{
		while (st.empty() == 0)
		{
			ans = ans + st.top();
			st.pop();
		}
		for (int i = ans.length() - 1; i >= 0; i--)
		{
			cout << ans.at(i);
		}
	}
}

shg9411 3년 전 2

+=연산은 ans.append(st.top())과 같이 실행되고,

ans = ans + st.top()은 ans+st.top()을 실행 후 ans에 새로 할당하는 것으로 알고있습니다.

bupjae 3년 전 1

대부분의 C++ 구현체에서

ans+=st.top(); 는

1) ans 의 여유 공간의 충분한지 확인한다

2) 충분하다면 ans 의 끝에 st.top() 를 추가한다

3) 충분하지 않다면 메모리를 메모리를 확보한 후 기존 ans 의 내용을 새로 확보한 메모리로 복사한 후 st.top() 를 추가한다.

이런식으로 동작할 가능성이 큽니다.

반면 ans = ans + st.top(); 는

1) 새로운 string 객체를 만든다

2) 만든 객체에 ans를 복사한다

3) 만든 객체에 st.top() 를 추가한다

4) 결과물을 ans 에 대입한다

이런식으로 동작할 가능성이 큽니다.

즉, ans = ans + st.top(); 의 경우 메모리의 복사가 ans+=st.top(); 에 비해 훨씬 많이 발생하면서 시간 효율이 나빠지게 됩니다.

pig07911 3년 전 0

감사합니다 형님들~~

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

문제

문제

출처

ICPC

string 질문이요!!

pig07911 3년 전 0

shg9411 3년 전 2

bupjae 3년 전 1

pig07911 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말