사부작사부작해요

주어진 문자열에서, 패턴(=폭발 문자열)과 일치하는 부분 문자열을 모두 삭제하는 문제이다. 문자열에 일치하는 패턴이 없을 때 까지 계속 반복한다. KMP로 풀어서 제출하면 시간초과로 통과하지 못한다. 패턴에 반복/공통되는 문자열이 없기 때문이다. 다른분들 풀이를 확인했는데, 스택을 많이 사용하더라. 폭발 후 문자열을 연속해서 폭발시킬 수 있어 논리가 단순해 스택을 많이 사용하는 것 같다. 왜 KMP가 안되는지, 왜 스택을 사용했는지, 특히 str 타입이 아니라 list 타입을 써서 해결한 이유는 뭔지 알아보자. KMP로 풀었을 때 문제를 다시 읽다보니, 조건에서 KMP로 풀지 말라고 알려주고 있었다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. KMP는 패턴에 공통 문자열이 많을수록 효과적인..