[백준 C++] 9935번 : 문자열 폭발

1. 문제

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

2. 알고리즘 분류

• 자료 구조
• 문자열
• 스택

 

3. 소스 코드

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 문자열 입력
	string s1, s2, ans = "";
	cin >> s1 >> s2;

	// 각 문자열 길이 계산
	int len1 = s1.length();
	int len2 = s2.length();

	// 문자열 탐색
	for (int i = 0; i < s1.length(); i++) {
    
		// ans 문자열에 한글자씩 담기
        ans += s1[i];
		
        // 폭발 문자열 길이 이상 문자열이 받아 졌을 경우, 폭발 문자열 포함 여부 확인
		if (ans.length() >= len2) {
			bool flag = true;
			
            // ans의 맨 뒤쪽 문자와 폭발 문자열과 비교
			for (int j = 0; j < len2; j++) {
				if (ans[ans.length() - len2 + j] != s2[j]) {
					flag = false;
					break;
				}
			}
			
            // 폭발 문자열일 경우 삭제
			if (flag)
				ans.erase(ans.end() - len2, ans.end());
		}
	}

	// 최종 답 출력
	if (ans.empty())	// 남아 있는 문자열이 없는 경우
		cout << "FRULA" << '\n';
	else
		cout << ans << '\n';

	return 0;
}

 

4.  상세 설명

1. 해당 문자열을 한 글자씩 읽음
2. 한 글자씩 읽다가 끝의 문자열이 폭발 문자열과 일치하는지 확인
3. 폭발 문자열과 일치한다면 문자열 삭제
4. 해당 문자열을 다 읽을 때까지 반복 (1 ~ 3번 반복)

4.1) 예시

1. 한 글자씩 ans에 담기
	ans = "m" -> "mi" -> ... -> "mirkovC4"

2. ans에 뒷 부분의 문자열이 폭발 문자열과 같은지 확인
	ans = "mirkovC4" => "C4"
    s2(폭발 문자열) = "C4"

3. 폭발 문자열과 같을 경우, 해당 문자열 삭제
	ans = "mirkovC4" => "mirkov"

4. s1(문자열)을 다 읽을 때 까지, 1 ~ 3번 반복

 

5.  문법

5.1) 문자열 뒷 부분 지우기

string str = "abcdefg";
int len = 3;	// 지울려는 문자열의 크기

str.erase(str.end() - len, str.end());