[BOJ] 9935번: 문자열 폭발

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

문제 자체는 단순합니다. 이걸 정말 마음편하게 코딩한다면 전체에 대해서 폭발 문자열이 있는지 확인하고 제거, 제거가 한번이라도 일어났다면 다시 전체에 대해서 폭발 문자열이 있는지 확인하고 제거 뭐 이런식으로 하면 되겠지만

CCCCCCCCCC....CCC444444......4444

C4

라는 입력에 대해 생각해보면 대략 O(N^2)이 필요해서 시간내에 풀 수가 없습니다.

대신에 스택을 활용하면 됩니다.

문자열을 입력받는 대로 스택에 넣는데, 스택에는 {문자, 현재 문자가 폭발문자열에서 이어지는 값}을 넣습니다. 예를 들어

ADBABCD

ABC

라는 예제를 생각해보면 스택에는

{A, 1} / {D, 0} / {B, 0} / {A, 1} / {B, 2} / {C, 3} / {D,0}이 들어가게 됩니다.

이 때 폭발 문자열과 같은 길이가 스택으로 들어온다면(위의 예제에서 {C, 3}) 3개를 pop합니다. 이 작업을 반복한 후 스택을 역순으로 출력하면 답이 됩니다. 시간복잡도는 O(N)입니다.

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