[BOJ] 3111번: CENZURA

https://www.acmicpc.net/problem/3111

맨 처음에는 문자열폭발 문제(http://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/103)와 거의 유사한 문제라고 생각을 했는데, 여기는 패턴의 문자가 서로 다르다는 조건이 없기 때문에 그 문제를 풀듯이 해결할 수가 없습니다. 그걸 깨달은게 어제 잠들기 직전이었고 패턴(A)의 길이가 25라는 점에서 착안, 그냥 linked list로 문자들을 엮어두고 앞 뒤에서 탐색하며 제거하는 식으로 해결하면 충분히 시간 내에 해결이 되겠다는 아이디어를 오늘 아침 떠올렸습니다.(KMP를 활용하면 O(TA) 대신 O(T+A)로 떨굴 수 있을 것 같습니다.)

그런데 정작 구현에서 엄청 애를 먹었습니다. 역순으로 탐색하는 부분은 reverse_iterator를 활용하려고 했는데, 제가 봤을땐 틀린게 없는데 제출하면 계속 런타임에러가 발생하고 어떤 경우에 런타임에러가 발생하는지도 찾지 못해서 소스를 그냥 갈아엎었습니다. 저녁 8시쯤부터 다 짜고나서 밥을 먹어야겠다고 생각했는데 2시간 반동안 붙들렸네요. 매우 배고픕니다.

https://github.com/blisstoner/BOJ/blob/master/3111.cpp