문자열 폭발

출처 : 백준 #9935

시간 제한	메모리 제한
2초(추가 시간 없음)	128MB

---

문제

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

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

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

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

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

---

입력

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

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

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

---

출력

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

---

입출력 예시

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

---

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

---

풀이

1. 생각 및 풀이 설명 (오답 코드에 대한 설명)

• 다음과 같은 생각의 흐름대로 코드를 구성하였다.

  • 1. 우선 string에 exp가 있다면 string의 길이 - i가 0과 같거나 작아질 때까지 while문을 돌린다.
  • 2. string 속에 있는 exp 를 제거하여 준다. (슬라이싱 이용)
  • 3. exp가 없으면 while문을 끝내고, 아니라면 1,2 과정을 반복한다.

• 문제점

  • exp in string 연산과 슬라이싱 연산의 시간이 오래걸려서 시간초과가 떠버렸다.
  • 문자열을 그대로 두고 접근하려면 슬라이싱 밖에 방법이 없으므로 새로운 방법을 고안해야 했다.
  • 새로운 방법은 바로 리스트에 원소를 하나하나 넣는 방법이다.

python code (최초 풀이 - 오답)

# 백준 9935번 문자열 폭발
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

string = input().rstrip()
exp = input().rstrip()

def solution(string, exp):
    m = len(exp)
    while exp in string:
        n = len(string)
        i = 0
        temp = ""
        while n - i> 0:
            if string[i:i+m] == exp:
                i += m
            else:
                temp += string[i]
                i += 1
        string = temp
        temp = string # UnboundLocalError
    return temp if len(temp) > 0 else "FRULA"

print(solution(string, exp))

2. 생각 및 풀이 설명 (오답 코드에 대한 설명)

• 다음과 같은 생각의 흐름대로 코드를 구성하였다.

  • 1. 리스트 temp에 string의 문자를 하나씩 넣는다.
  • 2. 만약 리스트의 길이가 폭발 문자열의 길이보다 같거나 크다면, 리스트의 마지막 원소와 폭발 문자열의 마지막 문자를 비교한다.
  • 3. 만약 위의 두 개가 같다면, 폭발 문자열의 길이만큼 원소를 역순으로 비교하여 모두 같으면 리스트에서 pop한다.
  • 1~3의 과정 반복.

• 느낀점

  • 문자열 문제를 풀 때 항상 해당 문자열을 변형하지 않고 슬라이싱으로 풀다보니 이번 문제도 그렇게 접근을 했는데, 슬라이싱이 많은 시간을 소요하다보니 시간초과를 피할 수 없었다.
  • 리스트에 원소를 하나씩 넣어 비교를 하면 슬라이싱보다 적게 소요가 됨을 다시 한 번 깨닫는 계기가 되었다.

python code (정답)

# 백준 9935번 문자열 폭발
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

string = input().rstrip()
exp = input().rstrip()

def solution(string, exp):
    n = len(string)
    m = len(exp)
    temp = []
    for i in range(n):
        temp.append(string[i])
        if len(temp) >= m:
            if temp[-1] == exp[-1]:
                flag = True
                # len(temp) = 8 -> 7, 6
                # len(exp) = 2  -> 1, 0
                for x in range(len(temp)-1, len(temp)-m-1, -1):
                    if temp[x] != exp[x-(len(temp)-m)]:
                        flag = False
                        break
                if flag:    # 만약 temp의 끝 부분들이 exp와 같다면 제거해야 함.
                    for y in range(m):
                        temp.pop()
    result = ""
    for i in range(len(temp)):
        result += temp[i]
    return result if len(result) > 0 else "FRULA"

print(solution(string, exp))

++

from sys import stdin
from collections import deque
input = stdin.readline
string = list(input().rstrip())
virus = list(input().rstrip())
n = len(virus)
r = []
for _ in string:
	r += [_]
	if r[-n:]==virus:
		r[-n:] = []

if len(r)==0:
	print("DOOMSDAY")
else:
	print("".join(r))