[BOJ] 9935. 문자열 폭발(Python)

9935번: 문자열 폭발

 

처음 풀었을 때 시간초과 나서, 다른 분 풀이 보고 스택을 써야한다는 아이디어를 얻어 다시 코딩해서 pass했다.

• 사용 자료구조 : 문자열 + 스택
• 코드 설명 아래 주석에 달아놓았다.
• 핵심 아이디어는
  • 폭발 문자열의 마지막 글자가 현재 탐색하는 문자와 같고,
  • 폭발 문자열과 스택에 폭발 문자열의 길이만큼의 문자열이 같다면,
  • 스택에서 폭발 문자열의 길이만큼 pop() 해준다.
• 마지막 문자까지 모든 탐색이 끝났을 때,
  • 스택에 남아있는 문자가 있다면 스택을 문자열 형식으로 출력하고,
  • 문자가 남아있지 않다면 "FRULA"를 출력한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

def solve():
    blen = len(bomb_temp)       # 폭발 문자열의 길이
    last_bomb = bomb_temp[-1]   # 폭발 문자열의 마지막 글자
    stack = []
    for char in temp:
        stack.append(char)
        if char == last_bomb and bomb_temp == stack[-blen:]:
            for _ in range(blen):   # 길이만큼 stack의 문자 삭제
                stack.pop()
    result = ''.join(stack)
    if result:
        return result
    else:
        return "FRULA"			# 남은 문자 없으면

# main
temp = input().strip()                # 전체 문자열
bomb_temp = list(input().strip())     # 폭발 문자열
print(solve())

---

• 시간 : 208ms / 메모리 : 185620kb
• 고찰 : 문자열 문제를 근래에 많이 안 풀어서 이번 주는 문자열 위주로 좀 파야겠다. 문자열은 뭔가 유형이 돌고 도는 문제들이 많으니 좀더 익숙해질 필요가 있겠다.