알고리즘 분류

: string, 스택

🥶어떻게 풀것인가에 대해

: 만약에 한자리 수가 있다고 차면
내가 만든 프로세스는 동작이 안됨.

mirkovC4nizCC44
m

아무생각 없이 코드를 작성하면 안됨.

🥶51점 코드

• 반례 bbbbb / b
• 왜 이렇게 짠 것인가?
  : 폭발문자열이 한자릿수인 경우에 대해서 생각을 못함.
  -> 시작부터 잘못됨.

잘못된 부분

한자리인 것을 캐치를 했다면, 이렇게 작성하지는 않았을 것임.

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <stack>

// 02:00 ~ 
// 문자열 폭발

int main()
{
	// 남은 문자열을 이어붙임. 


	// 문자열의 길이는 백만 이하임. 
	
	string target;
	cin >> target;

	string s;
	cin >> s;

	// s의 back이랑 하나의 iter가 동일 하다면
	// s의 문자열만큼 앞으로 이동하면서 비교를 하자. 

	// 12ab112ab
	// 11ab 라면? 
	// temp 변수에다가 저장해놓고, 
	// 리버스 해서 다시 반환? 
	// 실험을 해보아야 할 듯함. 

	stack<char>stk;

	for (int i = 0; i < target.length(); ++i)
	{
		// 매칭되지 않을 경우를 대비함.
		string temp = "";
		if (!stk.empty() && target[i] == s.back())
		{
			// 스택에 쌓여 있는 거랑 확인하기 
			bool check = false;
			for (int j = s.length() - 2; j >= 0; --j)
			{
				if (stk.top() == s[j])
				{
					temp += stk.top();
					stk.pop();
				}
				else
				{
					//하나라도 어긋 나면 불일치 하다는 것임. 
					check = true;

					// 스택에서 뺀 것 만큼을
					// 리버스해서 다시 push하자. 
					reverse(temp.begin(), temp.end());
					for (int a = 0; a < temp.length(); ++a)
					{
						stk.push(temp[a]);
					}

					break;
				}
			}
			// 매칭이 될 경우, 밑의 푸쉬 안하고, 다음원소로 진행하기
			
			if(check == false)
			continue;
		}

		stk.push(target[i]);
	}

	string res = "";

	while (!stk.empty())
	{
		res += stk.top();
		stk.pop();
	}

	if (res.empty())
	{
		cout << "FRULA";
		return 0;
	}
	
	reverse(res.begin(), res.end());
	cout << res;
}

💚find로 접근하면 시간 초과 발생함.

: 왜냐하면 문자열 길이 100만 까지이므로

💚풀이 전략

: 짝을 지어서 , 문자열을 지우는 문제임.

• 1) 타겟의 마지막 값과 일치하는 원소가 들어오면,
  어떤 temp에다가 타겟수만큼의 원소를 저장시킴.
• 2) 만약 temp와 타겟이 일치한다면 제거하고,
  그렇지 않다면, 리버스해서 다시 삽입을 함.

💚주의할 점.

: 타겟의 갯수만큼을 스택에서 팝을 할 것이므로,
타겟의 사이즈와 동일하거나 큰 지를 확인해야 함.

💚왜 스택이냐?

https://velog.io/@kwt0124/%ED%8F%AD%EB%B0%9C-%EC%A7%9D%EC%A7%93%EA%B8%B0-%EB%AC%B8%EC%A0%9C

첫번째 풀이

: 시간 초과 발생함.

#include <iostream>
#include <vector>
#include <string>
using namespace std;


int main()
{
	string s;
	cin >> s;

	string target;
	cin >> target;

	int idx = 0;

	// 타겟 못찾을 경우 뛰쳐나옴. 
	while (s.find(target) != string::npos)
	{
		auto iter = s.find(target); //발견된 인덱스를 나타냄.
		//cout << "찾음." <<  iter << endl;
		string ss = s.substr(0, iter);
		int next = ss.length() + target.length();	
		s = ss + s.substr(next);
		//cout << s << endl;		
	}

	//cout << "result : " << endl;
	if (s.empty())
	{
		cout << "FURLA";
	}
	else
		cout << s;
	
}

-> 다른 방법으로 풀어야 함.
그리디 하지 못했음.

고찰 : 왜 틀렸을까?

• 시간 초과
  : 왜냐하면 문자열 길이가 김. -> logN의 비용을 가지고 오도록 해야함.
  

find를 할 때마다 n의 비용으로 찾게 되므로 문제임.

• 결과
  : 다른 효율적인 방법을 생각해봐야 함.

문자열 문제는

• substr,
• size,
• erase
  를 잘 활용하자!

string의 find 시간 복잡도

https://rein.kr/blog/archives/373
: 좋지 못한 듯 함.

• 찾으면 찾은 문자의 인덱스를 반환 ,
  못찾으면 , string::npos를 반환함.

string의 erase

• 참고 자료 : 씹어먹는 c++
  https://modoocode.com/240

• 코드 : 중요함!

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main() {
	std::string s = "This is an example";
	std::cout << s << '\n';

	// erase 
	// 1번 : size_t start ~ size_t end 부분까지의 인덱스를 
	// 부분만을 지움!
	s.erase(0, 5);  // Erase "This "
	std::cout << s << '\n';

	//std::find 함수는 iterator를 반환함.
	s.erase(std::find(s.begin(), s.end(), ' '));  // Erase ' '
	std::cout << s << '\n';
	
	// string.find 함수는 
	

	s.erase(s.find("pl"));  // Trim from ' ' to the end of the string
	std::cout << s << '\n';

	s.erase(7);
	cout << s << endl;

	auto iter = s.find(' ');
	
	//s.erase(s.find(' '));  // Trim from ' ' to the end of the string
	s.erase(iter);  // Trim from ' ' to the end of the string
	std::cout << s << '\n';
}

• erase의 정의
  - 1번 사용 : substr( size_t start, size_t cnt) ;
  : 참조형식으로 되어 있는 듯해서, 범위 만큼의 문자가 지워짐.
  • 2번 사용 : substr( size_t idx);
    : idx 부터 마지막까지 전부다 지움!
  • 3번 사용 : substr( const_iterator pos);
    : pos위치에 있는 문자만 지움!

-> 느낀 점. erase 의 인자로 사용되는 것들에 따라서 지워지는 방식이
모두 다름.