boj 9935 : EKSPLOZIJA(문자열 폭발)

boj 9935 : EKSPLOZIJA(문자열 폭발)

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

시간초과를 저격한 문제.

1. 폭파문자가 있으면 폭파문자를 제거한다.

2. 폭파문자가 없을 때까지 1의 과정을 반복한다 

위의 방법으로 하면 시간초과.

다른방법을 생각해보아야 한다.

stack을 통해 구현하면 보다 편하다.

1. stack에 문자열을 담아간다.

2. stack의 윗부분이 bomb와 일치하면 bomb부분을 제거한다.

위의 방법으로 해결하면 문제가 풀린다.

stack의 윗부분이 bomb와 일치하는지 확인하는 과정도 bomb size의 만큼의 시간복잡도가 필요한데, 이 부분은 character 말고 int도 함께 stack에 쌓아주는 방법으로 접근하면 보다 빠르게 풀 수 있다.

stack의 top에 저장된 int형이 bomb size와 같을 때 bombsize만큼 pop해주면 된다.