백준 9935번 [문자열 폭발](C++)-yes6686- 티스토리

백준 문제 풀이: 9935 [문자열 폭발]

---

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

문제 설명:

문자열 S에서 특정 문자열 P가 나타날 때마다 제거하며, 모든 P가 사라질 때까지 반복합니다. 결과 문자열을 출력하며, 모두 사라졌다면 "FRULA"를 출력합니다.

입력:

• 첫째 줄에 문자열 S가 주어집니다. (1 ≤ |S| ≤ 1,000,000)
• 둘째 줄에 폭발 문자열 P가 주어집니다. (1 ≤ |P| ≤ 36)

출력:

• 모든 P를 제거한 후 남은 문자열을 출력합니다. 남은 문자열이 없다면 "FRULA"를 출력합니다.

---

문제 해결 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string s, bomb, result = "";
    cin >> s >> bomb;

    int bombLength = bomb.size();

    for (char c : s) {
        result += c; // 문자 추가
        if (result.size() >= bombLength && result.substr(result.size() - bombLength) == bomb) {
            result.erase(result.size() - bombLength); // 폭발 문자열 제거
        }
    }

    if (result.empty()) {
        cout << "FRULA" << '\n';
    } else {
        cout << result << '\n';
    }

    return 0;
}

예제

입력:
mirkovC4nizCC44
C4

출력:
mirkovniz

입력:
12ab112ab2ab
ab

출력:
12

---

코드 설명

• 문자열 처리:
  • 주어진 문자열 S를 한 문자씩 처리하며 result에 추가합니다.
  • 현재 result의 끝부분이 폭발 문자열 P와 같다면 제거합니다.
• 최종 결과:
  • 처리가 끝난 후 result가 비어 있으면 "FRULA"를 출력합니다.
  • 비어 있지 않다면 result를 그대로 출력합니다.

시간 복잡도

• 문자열 S의 길이를 n, 폭발 문자열 P의 길이를 m라고 하면, 시간 복잡도는 O(n)입니다.
• 문자열 추가와 비교는 효율적으로 처리되며, 최대 O(n)의 성능을 보장합니다.

---

결과

코드는 주어진 문자열에서 폭발 문자열을 효율적으로 제거하며, 최종 결과를 정확히 출력합니다. 스택 대신 문자열 조작을 통해 문제를 효과적으로 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!