백준 9935. 문자열 폭발

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

9935번: 문자열 폭발

 

단순히 폭발 문자열을 찾아 지우고, 처음 부터 다시 탐색해서 지우면 시간초과를 피할수 없다.

나는 스택에 현재 까지 탐색된 폭발 문자열의 길이를 저장해줬다.

 

예를들어 input이 다음과 같다면 

12ab112ab2ab
12ab

문자열을 처음부터 탐색하면 처음에 1은 폭발 문자열이기 때문에 스택에 1 저장.

 

이후 2를 탐색하는데, 현재 스택의 top에 1이 저장되있다. 그말은 즉 현재까지 폭발 문자열에 부합하는 문자열의 길이가 1이라는 것이고, 탐색중인 문자열 '2'는 bombStr[st.top()==1] = '2' 이기 때문에 폭발 문자열을 이어 갈수 있다.

따라서 스택에 숫자 2를 저장한다. 

 

이후 'a'를 탐색하는데 마찬가지로 스택의 top이 현재 2이기 때문에 bombStr[2]와 비교해서 스택에 푸쉬하면 된다. 

 

스택의 top 값이 폭발 문자열의 길이와 같아진다면 폭발 문자열이 완성된 것이기 때문에 그만큼 스택에서 빼주면 된다.

 

이렇게 하면 한 번의 탐색 즉 O(N)으로 해결할수 있다.