문제 링크

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

문제 설명

• 전체 문자열과 폭탄 문자열이 주어짐
• 폭탄 문자열이 존재하면 없애고 이어 붙임
• 반복 후 남은 문자열 출력

시도1

접근

• 길이가 100만인건 봤는데 그냥 find 함수 써서 구현했다
• 시간 초과가 났다
• O(N^2)이라 그런 것 같다
  • ex) 전체가 1111122222, 폭탄이 12일 때

코드

import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()
while True:
    result = []
    finished = True
    while True:
        i = string.find(bomb)
        if i < 0:
            result.append(string)
            break
        else:
            result.append(string[:i])
            string = string[i+len(bomb):]
            finished = False
    string = ''.join(result)
    if finished:
        break
if string:
    print(string)
else:
    print('FRULA')

시도2

접근

• 알고리즘 유형을 봤는데 스택이 있어서 생각해보니 떠올랐다
• 스택을 사용하면 삭제한 후 처음부터 다시 보지 않아도 된다
• 폭탄이 있으면 개수만큼 pop
• 없으면 append
• O(N)

코드

import sys
read = sys.stdin.readline
string = read().rstrip()
bomb = read().rstrip()

# 초기화
stack = []
i = 0
while True:
    # 길이가 넘고 같을 때 pop
    if len(stack) >= len(bomb):
        if ''.join(stack[len(stack) - len(bomb):len(stack)]) == bomb:
            for _ in range(len(bomb)):
                stack.pop()
    if i >= len(string):
        break
    # 다음거 append
    stack.append(string[i])
    i += 1

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