(백준) 3111 - 검열(실패)

타로에서 Ten of Swords는 사랑, 건강, 돈 등을 의미한다고 한다

검열은 사랑.. 돈?

---

문제

김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.

상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모두 없애려고 한다.

1. T에 A가 없으면 알고리즘을 종료한다.
2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
3. T에 A가 없으면 알고리즘을 종료한다.
4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
5. 1번으로 돌아간다.

상근이는 마을을 지배해야하기 때문에, 검열을 할 시간이 없다. 상근이의 검열을 대신해주는 프로그램을 작성하시오. 

입력

첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다.

출력

검열을 한 이후의 텍스트를 출력한다.

---

- 틀린 코드 (시간초과) -

정답률이 낮은 데에는 이유가 있었군

정 방향으로 한번 자르고,

뒤집어서 한번 잘라주는 방식으로 생각했는데,

sys.stdin.readline()을 이용해도 시간초과가 뜬다.

하긴.. 몇십만자를 뒤집었다 덮었다 해대니..

 

어! 묘수가 떠올랐다.

그리디 알고리즘에서 썼던 target을 이용해보면 되지 않을까?

3번이라면, 정2번 역1번 

4번이라면, 정2번 역2번 

5번이라면, 정3번 역2번

.....

N번이라면, 정(N/2)번 역(N/2)번 or 정(N+1/2)번 역((N+1/2) - 1)번

으로 짜보았으나 

banana

babananananadeda에서 막혔다.

 

아라라?

심상치 않은 문제였군..

 

힌트좀 얻어보려고 질문글 몇개 봤는데 아직 건드릴 문제가 아닌 것 같다.

문자열 폭발을 풀어보고 하라는 얘기가 좀 있네..

---