[백준/C++] 9935번 문자열 폭발 풀이

문제 해석

---

 

---

문제 풀이

---

우선 문자열은 100만 개라 O(N²)으로는 풀 수 없을 것 같았다.

문제에서 문자열을 찾아서 지워내면 되는 것이니 스택이나 정규식 풀이 방법이 먼저 떠올랐다.

mirkovC4nizCC44 에서 C4를 추려내는 등의 과정을 고려했더니 문자열을 비교할 때 어디까지 겹치는 문자열을 보유했었는지 저장하도록 하였다. (전에 문자열 알고리즘 중에 이런 게 있었는데 까먹었다.ㅎㅎ)

 

[로직]

1. 문자열과 폭발 문자열을 한 문자씩 비교하며 정답 문자열에 추가한다.
2. 문자가 같다면 폭발 문자열의 인덱스를 하나 증가시킨다.
3. 다르다면 지금 인덱스를 스택에 넣어 저장하고 현재 문자열부터 다시 비교한다.
4. 만약 인덱스가 폭발 문자열의 길이와 같다면 길이만큼 정답 문자열에서 제거한다.
   만약 이전 인덱스 스택이 비었다면 0을 아니라면 이전 인덱스 값을 받아온다.
5. 반복

[주의할 점]

1. 인덱스가 0에서 1로 넘어가는 순간에는 이전 문자가 다른 문자일 수도 있고 처음 시작하는 문자일 수 있으므로 인덱스가 일 때 따로 인덱스값을 한 번 더 저장시켜야한다.
2. substr은 생각보다 cost가 큰 함수이므로 주의해야한다.

---

코   드

---

#include <bits/stdc++.h>
using namespace std ;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    stack<int> indexs;
    string str, boom, words = "";

    cin >> str;
    cin >> boom;
    int idx = 0;
    for (int curr_idx = 0; curr_idx < str.length() ; curr_idx++) {
        if (boom[idx] == str[curr_idx]) {
            if (idx == 0) {
                indexs.push(0);
            }
            idx++;
        } else {
            indexs.push(idx);
            idx = (boom[0] == str[curr_idx]) ? 1 : 0;
        }

        if (idx == boom.length()) {
            // substr 시간초과: words = words.substr(0, words.length() - idx + 1);
            while(--idx) {
                words.pop_back();
            }
            if (!indexs.empty()) {
                idx = indexs.top();
                indexs.pop();
            } else {
                idx = 0;
            }
            continue;
        }
        words.push_back(str[curr_idx]);
    }

    words.empty() ? cout << "FRULA" : cout << words;

}

---

느낀점: 생각보다 알고리즘은 바로 떠올랐는데 구현이 맘처럼 쉽지가 않았다.

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

9935번: 문자열 폭발