[백준(BOJ)] 9935번 문자열 폭발 C++

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

9935번: 문자열 폭발

 

 

어떤 문제인가?

문자열과 폭발 문자열이 있다.

문자열에 폭발 문자열이 있으면 문자열에서 폭발 문자열을 지워 나가면 된다.

더 이상 폭발이 일어나지 않으면 남아있는 문자열을 출력하면 된다.

 

 

접근 방법

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

 

먼저 기준 문자열과 폭탄 문자열을 입력받는다.

ans는 빈스 트링으로 여기에 기준 문자열을 한 문자씩 추가해갈 것이다.

 

 

for (int i = 0; i < s.length(); i++) {
    ans += s[i];

    if (ans.back() == bomb.back()) {
        if (bomb.size() == 1) {
            ans.pop_back();
        } else {
            bool possible = false;
            for (int j = 1; j < bomb.length(); j++) {
                if (ans[ans.length() - j - 1] == bomb[bomb.length() - j - 1]) {
                    possible = true;
                } else {
                    possible = false;
                    break;
                }
            }
            if (possible) {
                for (int j = 0; j < bomb.length(); j++) {
                    ans.pop_back();
                }
            }
        }

    }
}

 

이제 반복문을 통해 연산을 진행할 것이다.

 

기준 문자열의 i번째 문자를 ans에 추가한다.

그리고 ans의 맨 끝 문자와 폭탄 문자열의 맨 끝 문자를 비교한다.

만약 이 둘이 일치한다면 ans에 폭탄 문자열이 존재할 확률이 있다는 것이다.

이제 이것을 어떻게 확인했냐면 폭탄 문자열의 길이만큼 반복문을 통해 ans의 있는 문자와 비교하는 것이다.

 

만약 폭탄 문자열이라면 문자 폭발 가능성의 여부를 나타내는 possible을 true로 바꾼다.

하나라도 일치하지 않는다면 ans에 폭탄 문자열이 없다는 뜻이므로 possible을 false로 바꾼 후 반복문을 탈출한다.

 

만약 폭발 문자열이 존재한다면. 폭탄 문자열의 크기만큼 ans를 pop 시켜주면 ans에서 폭탄 문자열이 사라질 것이다.

 

if (ans.empty()) {
    cout << "FRULA";
} else {
    cout << ans;
}

문제 조건에 맞게 문자열 폭발 후 남아있는 문자가 없다면 FRULA를 출력하고

그렇지 않다면 ans를 출력하면 끝이다.

 

 

 

무엇이 어려웠는가?

 

처음에는 시간 초과를 생각하지 않고 그냥 머리에 떠오르는 방법은 문자열의 문자 하나씩을 새로운 문자열에 추가한 다음 find함수를 써서 폭탄 문자열이 발견되면 폭탄 문자열의 크기만큼 pop 시켰다.

결과는 당연히 시간 초과.

find함수를 쓰지 않고 폭탄 문자열을 찾아내야 했다.

 

처음에는 문자열을 다 입력받은 후 그 안에서 폭탄 문자열을 제거해야 되는 방법을 생각했지만,

결국엔 입력을 받을 때 부터 폭탄 문자열이 있다면 지워나가는 방법을 생각할 수 있었다.

 

로직을 생각해내니 큰 어려움 없이 문제를 해결할 수 있었다.

 

 

배운 점

문제를 풀 때 처음에 꽃힌 생각에만 집착하지 말고 잠깐 물러서서 새로운 방법을 탐색해보자.

꼭 그 방법만이 정답이 아닐 수 있고 그 방법이 옳지 않을 수도 있다.