BOJ 9935 문자열 폭발

LONGNEW·2021년 3월 21일
0

BOJ

목록 보기
208/333

https://www.acmicpc.net/problem/9935
시간 2초, 메모리 128MB
input :

  • 문자열 (1 <= 문자열의 길이 <= 1,000,000)
  • 폭발 문자열 (1 <= 문자열 <= 36)

output :

  • 모든 폭발이 끝난 후 남은 문자열을 출력

조건 :

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
  • 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다.
  • 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

일단 data 배열로 입력을 받은 후에 data 배열을 가지고 줄여 나가면서 하려고 한다면, for문을 계속 돌려야 한다. 그런데 이 문자열의 길이가 100만 까지 들어오기 때문에 이건 좀 버겁다.

그렇다면 어떻게 할 까.... ans 배열을 만들어 놓고 제일 뒤에서 부터 확인 하면 되겠다.
그러면 언제 확인을 하게 시킬까.
새로운 문자를 추가했을 때 이 길이가 target 길이보다 길 경우에는 뒤에서 부터 target 길이만큼 확인을 하도록 시키고.

    if len(ans) >= len(target):
        start = len(ans) - 1
        for i in range(len(target) - 1, -1, -1):
            if ans[start] != target[i]:
                break
            start -= 1
        else:
            for i in range(len(target)):
                ans.pop(-1)

동일 한 경우에는 제일 뒤에서부터 삭제를 시키자
이 삭제시키는 것을 한 번에 못하는 가 하고 생각하고 있었는데 그냥 for문을 이용하도록 하자.

그리고 for - else문을 이용했다. break에 한 번이라도 걸리지 않았다면 -> target 문자열이 존재한다는 것이기에 바로 pop을 해주면 되겠다.

import sys

data = list(sys.stdin.readline().strip())
target = list(sys.stdin.readline().strip())

ans = []

for item in data:
    ans.append(item)

    if len(ans) >= len(target):
        start = len(ans) - 1
        for i in range(len(target) - 1, -1, -1):
            if ans[start] != target[i]:
                break
            start -= 1
        else:
            for i in range(len(target)):
                ans.pop(-1)

ans = "".join(ans)
print(ans if len(ans) > 0 else "FRULA")

0개의 댓글