9935. 문자열 폭발 - 스택. 파이썬

9935. 문자열 폭발

사용한 알고리즘 / 자료구조
1. 스택

접근한 방법
1) 입력받은 문자열을 스택에 삽입한다.

2) 폭발 문자열이 생성되었는지 비교한다.
3) 폭발 문자열이 생성되었을 경우 스택에서 폭발 문자열의 길이만큼 문자들을 뺀다.

어려웠던 점
마지막 폭파 처리를 리스트의 슬라이싱으로 처리했다가 시간초과.

느낀 점
시간 복잡도에 항상 유의해야 한다. 같은 결과값을 내는 연산이라면 가장 빠른 방법을 선택해야 한다.

풀었을 때의 백준 티어
2021-10-09. 골드 2.

import sys

# 1. 입력
# 둘 다 상수이므로 대문자로 표기한다.
INPUT_STRING = list(sys.stdin.readline().rstrip())  # 초기 문자열
BOMB = list(sys.stdin.readline().rstrip())  # 폭탄 문자열.

# 2. 선언
B_LENGTH = len(BOMB)    # 폭탄 문자열의 길이. 자주 사용되므로 상수처럼 값을 담아놓는다.
stack = []  # 연산을 위한 스택 선언

# 3. 연산
for syl in INPUT_STRING:    # 입력받은 문자열의 모든 문자들을
    stack.append(syl)   # 일단 스택에 넣는다.
    blow_up = True      # 폭발 여부 체크용 flag

    # 1) 예외 처리
    if len(stack) < B_LENGTH:   # 현재 스택의 길이가 폭탄의 길이보다 작다면
        continue    # 아래의 연산을 진행하지 않는다.

    # 2) 폭파 여부 확인
    for i in range(B_LENGTH):   # 폭탄 문자열과 스택의 앞부분을 순차 비교해서
        if BOMB[i] != stack[-B_LENGTH + i]:     # 한 글자라도 다른 부분이 있다면
            blow_up = False     # 폭발하지 않는다.
            break       # 폭발하지 않는 것이 확실하므로 더 이상 확인할 필요가 없다.

    # 3) 폭파 연산
    if blow_up: # 문자열이 폭발한다면
        for i in range(B_LENGTH):   # 폭탄의 길이만큼
            stack.pop()     # 문자열이 폭발한다.

# 4. 출력
if stack:  # 스택에 값이 있을 때
    print(''.join(stack))  # 출력 형식에 맞춰서 출력
else:       # 스택에 값이 없다면
    print('FRULA')  # 요구조건에 맞춰서 출력