[백준 | 골드4] 9935번: 문자열 폭발(스택, 정규식, 단어길이만큼비교)

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1 복사

mirkovC4nizCC44
C4

예제 출력 1 복사

mirkovniz

예제 입력 2 복사

12ab112ab2ab
12ab

예제 출력 2 복사

FRULA

 

문제해결

스택 사용

1. 입력 문자를 앞에서부터 하나씩 stack에 추가

2. 스택 꼭대기와 폭발 문자열 끝이 같은 경우 and 스택 꼭대기에서 폭발 문자 길이만큼 폭발 문자와 같은지 확인

3. 같은 경우 폭발 문자 길이만큼 스택에서 제거

 

다른분꺼 참고해서 풀었는데 이런 생각은 어떻게 하는가 너무 어렵다 ㅠㅠ

스택에서 문자열 길이 확인하는 것도 저렇게 하는것도 처음 알았다 ㅠㅠ

기억하고 있다가 다음에 꼭 써먹자

del도 잘 안쓰는데 이것도 써버릇 해야겠다 ㅠㅠ

bomb_string = input()

stack = []                      #스택에 입력문자열 string 하나씩 담음
bomb_len = len(bomb_string)     #폭발 문자의 길이

for i in range(len(string)) :   
    stack.append(string[i])     #스택에 입력 문자열 하나씩 담음

    #스택 꼭대기와 폭발 문자열 끝이 같은 경우
    #스택 꼭대기에서 폭발 문자 길이만큼 자른 문자열과 폭발 문자열 비교
    if stack[-1] == bomb_string[-1] and "".join((stack[-bomb_len:])) == bomb_string :
        del stack[-bomb_len:]   #같은 부분분 길이만큼 제거

result = "".join(stack)

if result == "" :
    print("FRULA")
else :

 

정규식으로도 풀수는 있더라 단 시간초과가 난다.

import re

s = input()
k = input()

while k in s :
    s = re.sub(k, '', s)    #re.sub（정규 표현식, 대상 문자열 , 치환 문자）
if len(s) == 0 :
    print("FRULA")
else :
    print(s)