백준 9935번 문자열 폭발

문제 설명

문자열과 폭발 문자열이 주어집니다.

문자열 내부에 폭발 문자열을 포함하고 있다면, 폭발 문자열이 폭발해서 사라지고 남은 문자열을 이어붙입니다.

이어 붙인 문자열이 폭발 문자열을 또 포함하고 있다면 폭발 문자열을 폭발하고 남은 문자열을 이어붙입니다.

문자열 내부에 폭발 문자열이 없을 때까지 반복합니다.

 

문제 풀이

아이디어

문자열 내부의 폭발 문자열 찾기

문제 예제에 있는 문자열 'CC44'에서 폭발 문자열 'C4'를 찾을 경우를 생각해보겠습니다.

 

폭발 문자열의 첫 번째 글자 'C'부터 차례대로 문자열 내부에 있는 폭발 문자열을 찾는다고 하면,

문자열의 인덱스 0에서 'C'를 찾게 되지만, 그 다음 글자가 'C'이므로 다음 인덱스로 넘어갑니다.

문자열의 인덱스 1에서 'C'를 찾게되고 인덱스 2가 '4'이므로 해당 폭발 문자열을 없앤 뒤 남은 문자열을 이어붙일 것입니다.

이어 붙인 문자열이 C4이지만 현재 찾고 있는 인덱스는 1이므로 더 이상 폭발 문자열을 찾지 못하고 종료하게 됩니다.

 

폭발 문자열의 마지막 글자 '4'부터 차례대로 문자열 내부에 있는 폭발 문자열을 찾는다고 하면,

문자열의 인덱스 2에서 '4'를 찾게 되고 인덱스 1이 'C'이므로 해당 폭발 문자열을 없앤 뒤 남은 문자열을 이어붙입니다.

그 다음 마지막으로 찾던 문자열이 1이므로 다시 문자열의 인덱스 1부터 폭발 문자열을 찾게 됩니다.

문자열 인덱스 1에서 '4'를 찾게 되고 인덱스 0이 'C'이므로 해당 폭발 문자열을 없앤 뒤 남은 문자열을 이어붙입니다.

 

위와 같이 폭발 문자열을 첫 번째 글자부터 찾는 것이 아니라 마지막 문자부터 찾게 될 경우, 폭발문자열을 제거한 뒤 마지막으로 있었던 인덱스부터 다시 폭발문자열을 찾을 수 있게 됩니다.

 

풀이

스택 활용

문자열을 첫 번째 문자부터 마지막 문자까지 탐색하면서 한 글자씩 스택에 넣어줍니다.

스택에 넣어줄 때에 해당 문자가 폭발 문자열의 마지막 문자와 같고 스택[-{폭발 문자열 길이}:]을 합친 문자열이 폭발 문자열과 같다면, 폭발 문자열과 같다면 해당 길이만큼 스택에서 원소를 pop해줍니다.

 

마지막까지 폭발되지 않고 남아있는 스택의 원소를 합친 문자열이 답이됩니다.

 

 

해결

어떤 두 가지를 비교할 경우 무조건 앞에서부터 비교할 필요가 없다는 것을 알려준 문제인 것 같습니다.

 

문제 링크 : https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/9935.py