[Python] 9935번 : 문자열 폭발

 

문제 3줄 요약

1. 문자열에서 지워야할 '폭발 문자열'이 라는 것이 있다.

2. 위의 3 가지 과정으로 폭발이 진행된다.

3. 폭발이 끝난 후, 남은 문자열을 출력하되 남은 문자가 없을 경우엔 "FRULA"를 출력한다.

 

 

 

 

Python에는 문자열에서 문자를 지울 수 있는

replace 함수가 존재하지만...

replace를 사용하여 구현한다면?

 

펑

 

시간 초과가 터져버린다.

 

최대 길이가 100만인 문자열을

replace로 지워가며

새로운 문자열까지 검색하는 과정이 있다보니

100만 * 검색횟수 만큼 시간이 소요된다고 생각된다.

 

그래서 생각해낸 방법은

 

이해를 돕기위해 허접한 그림판에 써보았다.

 

Input이 ACCBB고 폭발 문자열이 CB라면,

1차 폭발 후, ACB

2차 폭발 후, A가 될 것이다.

 

위 과정을 구현하기 위해

폭발 문자열의 마지막 문자인 B가

Check에서 보였을 때,

앞에 있던 문자열들이 폭발 문자열과 일치한지 검사한다.

 

맞다면,

폭발 문자열만큼 지워주고

다시 Input의 문자를 하나씩 Check에 넣어준다.

 

한번 넣었던 Input은 다시 넣지 않게

방문도 체크해주었다.

 

from sys import stdin

if __name__ == "__main__":
    # 폭발 문자열이 담긴 입력 값, 폭탄 문자열
    input_list = list(stdin.readline().strip())
    bomb_str = str(stdin.readline().strip())

    i, cnt, length = 0,0,len(bomb_str)
    result = []

    # 방문 표시
    visited = [ 0 for _ in range(1000000)]

    while(i != len(input_list)):
        # 방문 했다면, 패스
        if visited[i] == 1:
            i += 1
            continue

        spell = input_list[i]
        result.append(spell)
        visited[i] = 1

        # 폭발 문자열의 마지막 글자가 탐색된 경우
        # 주어진 문장보다 폭발 문자열이 길면 폭발할 경우가 없다.
        if (result[-1] == bomb_str[-1]) and (len(result) >= length):
            delete = 1
            
            # 폭발 문자열과 전부 일치하는지 검사
            for r in range(length):
                if result[-1-r] != bomb_str[-1-r]:
                    delete = 0
                    break
            
            # 전부 일치한다면, 삭제
            if delete:
                for r in range(length):
                    result.pop()
                if len(result):
                    i = i-(length+1)                   
                else:
                    i=0
        i += 1

    if len(result):
        print(''.join(result))
    else:
        print("FRULA")

 

이 외에도

고려해줘야할 부분이 꽤 많았지만,

통과!

 

 

끝