[백준] 9935번 문자열 폭발 (Python)

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

• 조금 난이도 있는 스택 문제였다. pop과 append를 필요할 때에 맞춰 사용하는 능력을 필요로한다. 

---

< 문자열 폭발 > 

[문제]

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

[입력]

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

[출력]

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력	예제 출력
mirkovC4nizCC44 C4	mirkovniz
12ab112ab2ab 12ab	FRULA

---

아이디어

폭탄 문자열인 것이 여러 개 겹쳐있을 때가 난관이었다. 어떻게 해결해야할 지 곰곰이 생각해보았다. 폭탄의 처음 인덱스부터 차례로 검사하게 되면 여러개 겹쳐있을 때 정확히 체크하기 상당히 어려웠다.(어떻게 해야할 지 구상하는 것 조차 어려웠음.)

예를 들어 예제입력 1번의 CC44부분을 생각해보자. 처음 C에서 폭탄의 0번 인덱스인 C와 일치하므로 다음을 체크하는데 다음의 C는 폭탄의 4와 일치하지 않으므로 폭탄과 다르다고 인식하게 된다.

그래서 생각을 바꾸어 폭탄의 마지막 인덱스부터 차례로 접근하며 체크해보는 것이었다. 그렇게 된다면, CC까지 왔을 때는 아무 일도 일어나지 않다가 CC4에 왔을 때 C4가 폭탄과 일치하므로 없어지고 C만 남게 된다. 그 후 다시 문자 4에 왔을 때 남아있던 C와 합쳐져 C4가 되고 이는 폭탄과 일치하므로 또 없어지게 된다. 문제의 요구대로 폭탄 문자열이 없을 때까지 폭발이 계속 되는 것이다.

풀이 및 코드

input_string = input()
bomb = input()
stack = []
for c in input_string:
    stack.append(c)
    # 인덱스 에러 방지를 위해 폭탄문자열의 길이가 더 길면 continue
    if (len(stack) < len(bomb)):
        continue
    # input_string에 하나하나 접근할 때마다 체크
    tmp = []
    # 폭탄 문자열과 stack의 뒷부분이 일치하는지 검사하는 for문
    for i in range(-1, -len(bomb) - 1, -1):
        # 폭탄문자열과 스택이 일치하지 않는다면 pop하지 않고 break
        if stack[-1] != bomb[i]:
            break
        # 일치한다면 pop해서 tmp리스트에 담아둠. (폭탄과 다른 문자열일 때를 대비한 임시저장소임.)
        tmp.append(stack.pop())
    # "tmp길이와 bomb길이가 다르다" 는 "break문을 실행하였다"와 의미가 같음.
    # 즉 스택에 있던 문자열과 폭탄 문자열은 다른 문자열이었다. -> 스택에 다시 append 해주며 원상복구시킴.
    if len(tmp) != len(bomb):
        while tmp:
            stack.append(tmp.pop())
if not stack:
    print("FRULA")
else :
    print("".join(stack))

처음의 if문을 넣어주지 않는다면 스택의 길이보다 큰 인덱스로 접근하게 되므로 indexError가 나게 된다.

for문 안에 len(bomb)만큼 반복하는 for문을 넣기에 O(N^2)인 것 같지만, bomb의 길이는 최대 36이고, 이는 결국 상수번 반복하는 것이다. 따라서 두번째 for문의 시간복잡도는 O(1)이라고 생각할 수 있다. (그 아래 while문도 마찬가지임. tmp는 항상 bomb보다 작거나 같음) 결국 이 프로그램의 시간복잡도는 O(N)인 셈이다. 대충 계산 개수를 생각해본다면 문자열의 길이가 100만이고, 폭발 문자열의 길이가 36이면 폭발문자열을 tmp에 저장 후 다시 stack으로 원상복구하는 경우가 72번 계산이므로 100만 * 72 = 7200만번 계산하는 것이다. 이 정도면 2초면 충분한 시간이라고 생각하였다.