[백준 / BOJ] 9935 문자열 폭발

문제

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

9935번: 문자열 폭발

문자열이 주어지고, 폭발 문자열이 주어진다.

 

문자열에서 폭발문자열이 있는경우 해당 폭발문자열은 사라지게된다.

 

예를들어,

 

CaaaabbbbC

ab

인경우

가운데 부터 순서대로 사라져서 마지막에

CC만 남게된다.

 

풀이

문자열의 최대길이가 백만이므로 일반적인 완전탐색으로는 시간초과가 난다.

 

스택의 특징을 사용해서 구현했다.

 

구현은 간단한데

1. 문자열을 하나하나 deq에 넣으면서 탐색한다.

 

2. 입력받은 문자열을 탐색하다가, 문자열[idx]가 폭발문자열의 끝과 같다면, 현재 인덱스를 기준으로 뒤로돌면서 폭발문자열인지 확인한다.

 

3. 해당 문자가 폭발문자열이라면 deq에 pop해준다.

 

이렇게 구현하면 항상성립하는데, 폭발문자열 사이에 폭발문자열이 있는경우, 더 늦게 만들어지기 시작한 폭발문자열이 항상 먼저 완성되기 때문이다.

예를들어, 폭발문자열이 bomb일때,

AbobombmbA 와 같은 문자열이 있다고 하자.

문자열을 순서대로 탐색할경우, deq에는

A -> Ab -> Abo -> Abob -> Abobo -> Abobom -> Abobomb 와 같은 순으로 push가 된다. 이때 사이에 있는 bomb가 사이에있는 bomb보다 빨리 나오는걸 볼수있다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9935%20%EB%AC%B8%EC%9E%90%EC%97%B4%20%ED%8F%AD%EB%B0%9C/main.cpp

devxb/JJUNalgo