Algorithm/Baekjoon

[Algorithm]Baekjoon 9935번 :: 문자열 폭발

MaxLevel 2022. 12. 15. 00:46

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

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    string s;
    string b;
 
    cin >> s >> b;
 
    string result = "";
 
    for (int i = 0; i < s.size(); i++)
    {
        result += s[i];
        
        int count = 0;
        int checkIndex = 1;
 
        for (int j = b.size() - 1; j >= 0; j--)
        {
            if (result[result.size() - checkIndex] == b[j])
            {
                count++;
                checkIndex++;
            }
            else break;
        }
 
        if (count == b.size())
        {
            for (int i = 0; i < count; i++)
            {
                result.pop_back();
            }
        }
    }
 
    if (!result.empty())
    {
        cout << result;
    }
    else
    {
        cout << "FRULA";
    }
}
 cs

 

빈문자열에 s를 하나씩 집어넣다가, 집어넣은게 폭발문자열의 끝문자랑 같으면 거기서부터 앞으로 하나씩 검사한다.

폭발문자열로 판명나면 그만큼 pop해준다음, 반복하면 끝.