[백준] 9935 - 문자열 폭발

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

9935번: 문자열 폭발

문제 한줄 이해

- 문자열이 있을 때 이 안에 폭발문자열이 들어 있으면 폭발해 해당 폭발 문자열이 삭제 되고 사라진다. 이때 최종 문자열 출력하기

생각난 풀이

1번째 방법: 먼저 문자열에서 폭발 문자열을 기준으로 split함수를 사용해 while 반복문을 통해 폭발문자열이 들어있지 않을때까지 연산하려고 했다.

import sys
senten = sys.stdin.readline().rstrip()
boom = sys.stdin.readline().rstrip()

while boom in senten: #폭발 문자열이 들어있으면 반복
    senten = ''.join(senten.split(boom)) #폭발 문자열 기준으로 split해주고 join을 하면서 진행
if senten == "":
    print("FRULA")
else:
    print(senten)

너무 쉬운데 왜 정답률이 25퍼이지? 하고 제출했더니 45퍼까지만 오르고 시간초과가 발생했다....

그렇다면 최대한 시간을 줄여봐야 한다.

우선 join함수는 문자열 길이의 영향을 받으니 리스트 범위 줄여보기, split함수 사용하지 않기

 

2번째 방법: 원본 문자열의 길이는 1000000이니깐 폭발 문자열의 길이를 최대한 사용해보고자 했다.

그래서 각 문자열의 문자를 result에 담아가면서

폭발문자열의 길이만큼만 join을 시켜 마지막에 위치한 것들이 폭발 문자열과 같으면 제거를 해나가도록 했다.

이때 result = result[:len(result)-len(boom)]를 통해 뒷부분은 빼주는 작업을 했지만 이또한 현재 result 길이의 영향을 받기때문에 boom의 길이를 이용할 수 있는 방법을 택했다.

 

import sys
senten = sys.stdin.readline().rstrip()
boom = sys.stdin.readline().rstrip()

result = []

for i in senten:
    result.append(i)
    if len(result) >= len(boom):
        if ''.join(result[len(result)-len(boom):len(result)]) == boom:
            #result = result[:len(result)-len(boom)]
            for k in range(len(boom)):
                result.pop()
if len(result) == 0:
    print("FRULA")
else:
    print(''.join(result))

시간 초과가 발생한다면 최대한 범위가 좁은쪽을 활용해보기....!!!!!!!!!!!!!!!!!!!!!!!