문자열폭발.md

DONE_DATE	2024/01/10

문자열 폭발

난이도

• 골드 4

문제

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

알고리즘 분류

• 자료 구조
• 문자열
• 스택
• string 연산 ?

오답코드

a = input()
b = input()

while a.find(b) != -1:
    a = a.replace(b, "")

if len(a) == 0:
    print("FRULA")
else:
    print(a)

• 위 코드는 시간초과가 발생한다.
• replace 함수는 O(n) 시간복잡도를 가지기 때문에, O(n^2) 시간복잡도를 가지게 된다.

정답코드

#include <bits/stdc++.h>

using namespace std;

string remove(string &input, string &bomb) {
    string result;
    for (char i : input) {
        result.push_back(i);
        if (result.size() >= bomb.size() && result.substr(result.size() - bomb.size()) == bomb) {
            result.erase(result.size() - bomb.size());
        }
    }
    return result.empty() ? "FRULA" : result;
}

int main() {
    string input;
    cin >> input;
    string bomb;
    cin >> bomb;
    cout << remove(input, bomb);
}

회고

• 스택을 이용해서 풀 수 있는 문제였다.
• 근데 굳이 스택이라고 하기보다는 구현에 가까운 느낌?
• remove 함수를 만들어서 풀었는데, 이 함수는 input 문자열에서 bomb 문자열을 제거하는 함수이다.
• result 문자열에 input 에서의 문자열을 하나씩 넣어주면서, 만약 result 문자열의 끝에서 bomb 문자열이 나오면 bomb 문자열을 제거해주었다.
• 연쇄적으로 폭발(문자열을 제거 했을때 뒤 문자열에서 폭발을 할 문자열이 발생하는) 그런 경우는 없다
• CC44 를 예를 들면 C, C, 4 에서 이미 제거가 일어나기 때문에 4가 폭발할 일은 없다. 이미 제거가 되었기 때문
• 골드 4치고는 너무 쉬운 문제인거 같다.