[AC] 9935 문자열 폭발

출처 : https://www.acmicpc.net/problem/9935

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/9935.cpp

이 문제는 참 좋은 문제였다. 얼핏보면 매우 간단한 문제로 보였다. 그러나 자꾸 시간초과가 났고, 결국 문자열길이가 최대 백만이라는 점이 문제가 되고 있음 을 깨달았다.

초기 알고리즘은 폭발문자열을 찾고 그부분을 지우고 다시 찾고 지우고 이런식으로 진행했다. 생각해보니 찾는다는것 자체가 백만이라는 가정하에 너무도 늦게 찾을것 같았다.

그래서 생각한것이 스택처럼 다루는 것이다. 문자열을 하나씩 추가하고 끝문자를 기준으로하여 만약 폭발문자의 끝문자와 현재 스택으로쓰는 스트링의 끝문자가 같다면 폭발문자열과 같은지 그때만 비교를 하는것이다. 같다면 인덱스값을 조절하여 다시 저장하게 하는 방식으로 진행하였는데, 이렇게하니 상당히 빠른 속도를 보이며 정답을 맞았다.

이 키워드를 얻은 계기는 폭발문자열이 최대 40문자가 안된다는 점이었다. 그렇다면 폭발문자열만 자주 사용해주어도 되겠다고 생각하여 진행하였다.

참 괜찮은 문제라고 생각한다.