[백준] 9935번 - 문자열 폭발 / 골드4 / 파이썬 풀이

문제 링크

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

9935번: 문자열 폭발

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• 문자열 속에 '폭발 문자열'이 존재하면 해당 문자열은 삭제됨.
  (문자열 : 입력으로 주어짐 / 폭발 문자열 : 입력으로 주어짐)
• '폭발 문자열'이 폭발하면, 즉, 사라지고 나면 남은 문자열은 순서대로 이어 붙임.
• 이렇게 이어 붙여진 문자열에 폭발 문자열이 또 포함되어 있을 수 있음.
• 폭발 문자열이 문자열에서 사라질때까지 폭발이 계속됨.
• 제약사항
  - 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않음.
  
  
• 문제 : 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구한다.
  
  
• 종료 조건
  - 폭발 문자열이 사라지면 종료됨.
  - 모든 문자열이 폭발되면 "FRULA" 를 출력.

 

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

예제 입력 1

mirkovC4nizCC44
C4

예제 출력 1

mirkovniz

 

예제 입력 2

12ab112ab2ab
12ab

예제 출력 2

FRULA

---

풀이

 

"폭발 문자열의 맨끝 문자의 일치여부만 조건문으로 넣어도, 문자열을 일일히 다 비교하지 않아도 된다!"

"""
    1. 입력문자열을 앞에서부터 차례차례 한 글자씩 스택에 push 합니다.
    2. 현재 글자가 폭발 문자열의 마지막 글자와 일치하면 
스택의 top부터 폭발문자열의 길이까지 확인하여 폭발문자열이 만들어지는지 확인합니다.
    3. 폭발문자열이 만들어진다면 만들어지는 폭발문자열을 스택에서 pop합니다.
    4. 1~3을 반복합니다.
    5. 문자열 순회를 마치고 스택이 비어있으면, FRULA를 출력, 비어있지 않다면 스택 속 문자열을 차례로 출력합니다.
"""
 
def main():
 
    string = input()    # 전체 문자열
    bomb = input()      # 폭발 문자열
 
    bomb_lastChar = bomb[-1] # 폭발 문자열의 마지막 글자
    stack = []
    bomb_length = len(bomb)  # 폭발 문자열의 길이
 
    for char in string:
        stack.append(char)		# 한 글자씩 스택에 넣기.
        if char == bomb_lastChar and ''.join(stack[-bomb_length:]) == bomb:
        # 현재 스택에 넣은 문자가 폭발 문자열의 맨끝 문자와 일치하고,
	# 스택에서 폭발문자열의 길이만큼 문자열을 추출했을 때, 이 문자열이 폭발문자열과 일치한다면
            del stack[-bomb_length:]			# 해당 문자열을 스택에서 제거한다.
 
    answer = ''.join(stack)
 
    if answer == '':
        print("FRULA")
    else:
        print(answer)
 
 
if __name__ == '__main__':
    main()

 

참고

https://mytodays.tistory.com/23

[백준 9935] 문자열 폭발 - python