문제

문제 링크

문제 접근

  • 처음에는 문자열에서 폭발 문자열이 존재하지 않을 때까지 폭발 시키기를 반복하고 결과를 출력하였다.
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s, bomb;
    cin >> s >> bomb;
    while(1){
        string::size_type n = s.find(bomb);
        if(n == string::npos)break;
        s = s.substr(0, n) + s.substr(n + bomb.length(), s.length() - 1);
    }
    if(s.length() != 0)cout << s;
    else cout << "FRULA";
}
  • 결과는 당연한 시간초과였다.
  • 시간 초과를 해결하기 위한 방법을 추석 틈새마다 고민해도 떠오르지 않았다.
  • 결국 오늘 stack을 이용하는 방법에 대한 힌트를 보고 문제를 풀 수 있었다.

효율성 높이기

  • stack에 글자를 넣으면서 현재 stack 꺼내는 문자가 폭발 문자열의 역순과 같은지 확인한다.
  • 같으면 넣지 않고 다르다면 빼냈던 문자를 다시 stack에 넣어준다.
  • 처음에 stl에 있는 stack을 사용했다. 하지만 마지막에 문자를 출력하기 위해서 stack에서 문자를 일일이 꺼내서 정답 문자열 앞에 추가시켜줘서 출력해줘야 했다.(stl에 있는 stack은 indexing이 안된다.)
  • 이를 해결하기 위해 그냥 stack도 직접 구현해서 indexing해서 하나씩 출력했다!

코드

#include <cstdio>
#include <string.h>

using namespace std;
int main(){
    char s[1000003], bomb[40], temp[40], stack[1000002];
    scanf("%s %s", s, bomb);
    int top = 0, sn = strlen(s), bn = strlen(bomb);
    for(int i = 0; i < sn; i++){
        stack[top++] = s[i];
        int cnt = 0;
        for(int j = bn - 1; j >= 0; j--){
            if(bomb[j] != stack[top-1]) break;
            temp[cnt++] = stack[--top];
        }
        if(cnt == bn)continue;
        for(int j = cnt - 1; j >= 0; j--)stack[top] = temp[j], top ++;
    }
    if(!top)printf("FRULA");
    else for(int i = 0; i < top; i++)printf("%c", stack[i]);
}

느낀점

  • stack을 이용해서 기가 막히게 시간을 단축하는 방법을 발견한 고수님께 공을 돌린다.
  • stl이 항상 답은 아니다. 웬만한거는 내가 구현하는 것도 좋을 것 같다.