[BAEKJOON]9935 문자열 폭발 - Python

문제 요약

• 알고리즘 분류: 스택, 문자열
• 난이도: Gold4
• 문제내용:
  • 문자열 주고 위에 조건에 맞게 폭발 문자열을 제거한후 문자열을 출력해라
  • 폭발 문자열 제거후 문자열이 없으면 "FRULA"를 출력해라
• 사이트: https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

문제풀이

string = input()
explore_string = input()
lenth = len(explore_string)
while string.count(explore_string):
    string = string.replace(explore_string, "")
    
print(string if string else "FRULA")

 문제가 간단해보여서 replace 함수를 사용해서 폭발 문자열을 제거하면 시간초과가 나올것이다. 그 이유는 문자열 최대 길이 100만인 점에서 폭발 문자열이 없어질때 까지 처음 부터 끝까지 탐색해야 한다는 점에서 O(N ^ 2)이라는 시간 복잡도가 나오기 때문이다.

문제 접근 방법

 완전 탐색 방법으로 제거하기에는 무리가 있기 때문에 stack이라는 자료구조를 이용할것이다. stack에 대한 설명은 여기에서 확인 하면된다.

  스택으로 어떻게 구현 하면  문자열 앞에서 부터 추가하고 나서 스택의 뒤 부분과 폭발 문자열이 포함되면 제거 하는 식으로 갈것이다. 그러면 O(N)탐색으로 통과가 될것이다. 말은 간단하지만 이해 하기 쉽도록 예제 1번 가지고 예시를 들겠다.

 위 그림은 스택을 저장한 과정을 표로 나타 낸것이다. 일단 1 부터 6번까지는 그냥 추가이다. 그다음에 7번 라인 부터 보면 폭발 문자열 'C4'와 맨 뒤에 문자열 'C4'가 일치하다 그러면 그 문자열을 제거를 한다. 그다음 12번 까지는 추가 되다가 13은 일치하기 때문에 뒤에 'C4'를 제거 하고 나면 다음 14번에 4를 추가하니까 'C4'가 나왔서 제거를 하면 된다.

 

Code

Python

string = input()
explore_string = input()
lenth = len(explore_string)
stack = []
for s in string:
    stack.append(s)
    if len(s) <= len(explore_string) and ''.join(stack[-lenth:]) == explore_string:
        for _ in range(lenth):
            stack.pop()
string = ''.join(stack)
    
print(string if string else "FRULA")

마무리

이번 문제는 스택 응용 대표적인 문제이다. 코태 준비한다면 풀어보는것을 추천한다.