백준 문자열 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42578

[나의 풀이1]

⌛ 5분 소요 (해결X, 테스트 케이스 시간초과)

str1 = input()
bomb = input()

while bomb in str1:
    str1 = str1.replace(bomb,"")

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

가장 간단한 형태로 시도했지만 일부 케이스에서 시간초과가 났습니다. 이를 보고 자료구조를 통해 해결하고자 하였습니다.

[나의 풀이2]

⌛ 55분 소요 (해결X, 테스트 케이스 시간초과)

str1 = input()
bomb = input()

from collections import deque
import itertools
str1 = deque(str1)
n_bomb = len(bomb)

origin_str1 = deque(str1.copy())
str1.rotate(1)

while origin_str1!=str1:

    if ''.join(list(itertools.islice(str1, 0,n_bomb)))==bomb:
        for _ in range(n_bomb):
            str1.popleft()
        origin_str1 = deque(str1.copy())
    str1.rotate(1)


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

queue 구조로 문자열폭탄의 길이만큼 popleft()하며 문자열을 수정해가는 지워가는 풀이입니다. 위 코드로 문자열폭탄들은 없어지지만 queue구조로 돌아가다 보니 순서는 맞지 않는 경우가 생겨 해결하지 못하였고 다른 풀이를 참고하였습니다.

[다른사람의 풀이1]

# 개선 답안
import sys

# 입력값 처리
S = sys.stdin.readline().rstrip()
explosion_string = sys.stdin.readline().rstrip()

# stack으로 문자열 폭발 구현
stack = []
ex_len = len(explosion_string)

for i in range(len(S)):
    stack.append(S[i])
    if ''.join(stack[-ex_len:]) == explosion_string:
        for _ in range(ex_len):
            stack.pop()

# 결과 출력
if stack:
    print(''.join(stack))
else:
    print('FRULA')

제가 접근한 유사한 방식의 풀이이되 stack 구조로 순서를 지키면서 문자열폭탄을 제거하는 구조입니다. 초기화된 stack 에 문자열을 순차적으로 append()하며 문자열 폭탄여부를 확인한다면 순서를 지킬 수 있었습니다.

[다른사람의 풀이2]

def main():
 
    string = input()    # 전체 문자열
    bomb = input()      # 폭발 문자열
 
    lastChar = bomb[-1] # 폭발 문자열의 마지막 글자
    stack = []
    length = len(bomb)  # 폭발 문자열의 길이
 
    for char in string:
        stack.append(char)
        if char == lastChar and ''.join(stack[-length:]) == bomb:
            del stack[-length:]
 
    answer = ''.join(stack)
 
    if answer == '':
        print("FRULA")
    else:
        print(answer)
 
 
if __name__ == '__main__':
    main()

'다른 사람의 풀이2'와 같은 방식이지만 세부적인 조건을 추가하여 더 빠르게 해결하는 풀이입니다. 문자열 폭탄의 마지막 글자(lastChar)를 방금 append한 글자인지 확인하여 아니라면 and 뒤 조건문

''.join(stack[-lenght:])==bomb:

을 바로 생략하는 방식입니다. 이렇게 섬세한 조건문을 통해 알고리즘의 속도를 향상 시킬 수도 있구나라는 것을 깨닫게 해주는 풀이였습니다.

감사합니다.